Stack Bash - Master data structures and algorithms

Binary Tree

A binary tree is a tree where each node has at most two children.
In a binary tree, each parent node's children are pointers to left and right nodes.
Binary Tree Example
In the example binary tree above, the node with 6 has two child nodes:
  1. The left child node is -4.
  2. The right child node is 7.

Binary Tree Traversal

Using the same example binary tree, let's go over the 3 ways to traverse a binary tree:
  1. In order traversal visits nodes in the order left, root, and right: -4, 6, 7, 9, 1, 8
  2. Pre order traversal visits nodes in the order root, left, and right: 9, 6, -4, 7, 1, 8
  3. Post order traversal visits nodes in the order left, right, and root: -4, 7, 6, 8, 1, 9

Binary Tree Big O

The leaves in a binary tree are the last nodes that can be traversed to from the root that have no children nodes
Given h that represents the height of the tree, or the distance between the root and the leaf node, the time complexity of traversing to a leaf node is O(h).

Binary Search Tree

A binary search tree (BST) is a binary tree of sortable elements that satisfies the following criteria:
  1. All elements on the left subtree are less than the parent node.
  2. All elements on the right subtree are greater than the parent node. BSTs that allow duplicates are often included as part of the tree's definition. For example, the values on the right are greater than or equal to the parent node.
Searching for elements in a binary search tree generally takes O(h) if the tree is relatively balanced, and O(n)in the worst case.

9 Essential Trees & Graphs Coding Interview Problems

Master Trees & Graphs by trying the coding challenges below.
  1. 1.Inorder TraversalEasy
  2. 2.Tree SumEasy
  3. 3.Tree HeightEasy
  4. 4.LCAMedium
  5. 5.Max Path SumHard
  6. 6.Search mazeMedium
  7. 7.Number of islandsMedium
  8. 8.Kth SmallestMedium
  9. 9.Sort K ArraysHard

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.