DEV Community

Brittany Javalera
Brittany Javalera

Posted on • Edited on

3

Data Structures - Pt 3 : Binary Trees

For me, binary trees are the most difficult data structure to comprehend, possibly because they are not a linear data structure. I am still not the expert on this data structure but I want to share what I have learned for other beginners.

Binary trees have nodes that hold data and a reference to their children.

  • The top node of a binary tree is referred to as the root node. It is the only node without a parent.
  • In a binary tree, each node can only have 2 immediate children(one left child, one right child).
  • A child is any node directly underneath a given node.
  • Nodes on the same level of a tree that share the same parent node are referred to as siblings.
  • A node that doesn't have children(bottom node) is referred to as a leaf.

Alt Text

One specific type of binary tree is a Binary Search Tree.

  • In a binary search tree, the left child will always be less than the parent node and the right child will be greater than the parent node.

Iterating through the elements of a tree is called Tree Traversal. There are 2 main ways to traverse through a tree:

  1. Breadth-First Search - iterates through each level of a tree from left to right
  2. Depth-First Search - iterates through elements starting from the root, down to the root's left child, down the left child's left child, and so on until it reaches the left leaf. Then it backtraces to the parent and down to the right child and so on until it backtraces to the root. The process then starts again with the root's right child. For example, in the binary search tree above, using depth-first search would go traverse the tree in the following order: [ 20, 14, 9, 3, 11, 19, 57, 31, 62, 72 ]

If you have any suggestions for basic information to add, or any resources to help learn more about binary trees, please do not hesitate to comment!

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more →

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up