Binary Search Trees & Tree Traversal

Binary Search Trees & Tree Traversal

Today I’m going to cover the two most common ways of traversing or iterating through the contents of a data structure known as a?Binary Search Tree. These are known as Breadth First Traversal (BFT) and Depth First Traversal (DFT). But before we get started

What is a Binary Search Tree?

A binary search tree is a data structure composed of nodes that each contain a piece of data, and a reference to two child nodes, the left child and the right child. The left child node’s data must always be smaller than the data of the parent node, and the right child node’s data must be larger than that of the parent node. Also, something important to note, when creating a binary search tree we must define a root node, which represents the base of the tree and thus the midpoint of all of the other nodes’ values. We end up with a tree structure of nodes, each with two children at the most.

No alt text provided for this image

As you can see, the right side of the tree contains nodes with data values that are all larger than the root node, and the left side contains nodes with data values that are all smaller than the root node.

Breadth First Traversal (BFT)

Breadth first traversal is a technique for traveling through a tree data structure by moving from the left to right through each row of nodes and down to the next row after the current row is complete. Here’s a nice illustration for clarity:

No alt text provided for this image
BFT


We travel from the root node ‘F’ down to the next row and reach ‘B’ after that ‘G’, then continue to the next row and hit ‘A’, ‘D’, then ‘I’ and so on. Breadth first search is a great tool to reach for if you are looking to find a node that is somewhat close to the root node.

Depth First Traversal (DFT)

Depth first traversal, the other common tool for moving through the elements of a tree, is done by first traveling down the left most branch of the tree until it hits the bottom of the tree. Once at the bottom, it will operate on each sibling of the left most child of the tree. Then the process will travel back up to the closest parent node, then operate on the next child of that node and all of its descendants. It continues to move down each path of the tree to the very bottom until all paths have been traveled. A bit confusing when written, but here’s a clear diagram:


No alt text provided for this image
DFS


The depth-first traversal path is simple to understand if you follow the path of the dotted line. It goes from left to right, scanning every branch for its deepest point before moving on. If you are looking for a node in your tree that could be extremely far down in the tree structure, depth-first search is fantastic.


I've finished my tour of the binary tree traversal! I hope this enables you to climb some digital trees like the real Donkey Kong ;)

要查看或添加评论,请登录

Ahmed Safwat的更多文章

  • Service Discovery Pattern: The Secret Behind How Microservices Call to Each Other

    Service Discovery Pattern: The Secret Behind How Microservices Call to Each Other

    It all started during a casual lunch break with the team. Our team leader, Fahmy looked frustrated as he stared at his…

    1 条评论
  • Reverse Proxy VS. API Gateway

    Reverse Proxy VS. API Gateway

    It all started during a casual team break. I had been reading some articles online about API Gateways, and a question…

    3 条评论
  • A Journey of Discovery and Decision “API Gateway”

    A Journey of Discovery and Decision “API Gateway”

    It was a regular Monday meeting — one of those where everyone was settling in, coffee cups in hand, waiting for Khaled…

    12 条评论
  • A Tale of Saving White Friday …

    A Tale of Saving White Friday …

    Disclaimer: This is a fictional story created to illustrate the Outbox Pattern. Any resemblance to real people, events,…

    1 条评论
  • Command Your Queries: Unraveling the CQRS Advantage

    Command Your Queries: Unraveling the CQRS Advantage

    Introduction to CQRS Command Query Responsibility Segregation (CQRS) is an architectural pattern that separates the…

    4 条评论
  • Spring Boot Projections Uncovered: How to Fetch Just What You Need

    Spring Boot Projections Uncovered: How to Fetch Just What You Need

    Spring Boot, powered by Spring Data JPA, simplifies the development of data-driven applications. One of its powerful…

    3 条评论
  • BIGINT vs. BIGSERIAL in PostgreSQL

    BIGINT vs. BIGSERIAL in PostgreSQL

    In PostgreSQL, managing large integers efficiently is crucial for many applications, especially when dealing with…

    1 条评论
  • ORM: The Database Magician

    ORM: The Database Magician

    the realm of software development, databases are an indispensable component for storing and managing data. Relational…

    2 条评论
  • Query Plan in a Nutshell

    Query Plan in a Nutshell

    Working with large databases often comes with the challenge of slow query performance. The root cause of this problem…

  • Discover the Secrets of Java Reflection

    Discover the Secrets of Java Reflection

    Java Reflection is a powerful feature in the Java programming language that allows developers to inspect and manipulate…

    3 条评论

其他会员也浏览了