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.
In the example binary tree above, the node with
6 has two child nodes:- The
leftchild node is-4. - The
rightchild node is7.
Binary Tree Traversal
Using the same example binary tree, let's go over the 3 ways to traverse a binary tree:
- In order traversal visits nodes in the order left, root, and right:
-4, 6, 7, 9, 1, 8 - Pre order traversal visits nodes in the order root, left, and right:
9, 6, -4, 7, 1, 8 - 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:
- All elements on the left subtree are less than the parent node.
- 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.Inorder TraversalEasy
- 2.Tree SumEasy
- 3.Tree HeightEasy
- 4.LCAMedium
- 5.Max Path SumHard
- 6.Search mazeMedium
- 7.Number of islandsMedium
- 8.Kth SmallestMedium
- 9.Sort K ArraysHard