Skip to main content

Binary Search Trees (BST)

https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

common questions
bst

Source:

Medium

Time Complexity​

OperationBig-ONote
AccessO(log(n))
SearchO(log(n))
InsertO(log(n))
RemoveO(log(n))

In-order Traversal​

Returns a sorted list.

Algorithm for In-order:
    1. Traverse left subtree -> call Inorder(node.left)
    2. Visit node
    3. Traverse right subtree -> call Inorder(node.right)

Pre-order Traversal​

Used to create a copy of the tree.

Algorithm for Pre-order:
    1. Visit node
    2. Traverse left subtree -> call Preorder(node.left)
    3. Traverse right subtree -> call Preorder(node.right)

Post-order Traversal​

Used to delete a tree.

Algorithm for Post-order:
    1. Traverse left subtree -> call Postorder(node.left)
    2. Traverse right subtree -> call Postorder(node.right)
    3. Visit node

Example Solutions​

Kth Smallest Element in a BST​

Solution 1: Find in-order array of BST​

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def kthSmallest(self, root, k):
  def findInorder(root, arr):
    if not root:
      return
    findInorder(root.left, arr)
    arr.append(root.val)
    findInorder(root.right, arr)
  arr = []
  findInorder(root, arr)
  return arr[k-1]

Time Complexity: O(n) for traversing the entire binary tree.

Space Complexity: O(n) for the in-order array.

Solution 2: Iterative solution​

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def kthSmallest(self, root, k):
  stack = []
  curr = root
  while curr or stack:
    while curr: # Find most left node
      stack.append(curr)
      curr = curr.left
    curr = stack.pop()
    k -= 1
    if k == 0:
      return curr.val
    curr = curr.right

Time Complexity: O(n) for traversing the entire binary tree.

Space Complexity: O(n) for the recursion stack.


Maximum Depth of Binary Tree​

A common approach to this question is to traverse by level.

Solution 1: Recursive Approach​

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def maxDepth(self, root):
  if not root:
    return 0
  return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Time Complexity: O(n) for traversing the entire binary tree.

Space Complexity: O(n) for the recursion stack.


Solution 2: Iterative Approach​

  • A stack to store the order of nodes to traverse
  • Keeping track of the number of nodes in a level
def maxDepth(self, root):
  height = 0
  level = [root] if root else None # stack of nodes in the level
  level_size = 1
  while level:
    node = level.pop(0)
    if node.left:
      level.append(node.left)
    if node.right:
      level.append(node.right)
    level_size -= 1
    if level_size == 0: # move on to next level
      height += 1
      level_size = len(level)
  return height

Time Complexity: O(n) for traversing the entire binary tree.

Space Complexity: O(log(n)) for the stack of nodes in the level.


Construct Binary Tree from Preorder and Inorder Traversal​

An excellent question to test your understanding of preorder and inorder traversal.

Solution: Recursive Approach​

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def buildTree(self, preorder, inorder):
  if inorder:
    i = inorder.index(preorder.pop(0)) # get index of root in inorder
    root = TreeNode(inorder[i])
    root.left = self.buildTree(preorder, inorder[:i])
    root.right = self.buildTree(preorder, inorder[i+1:])
    return root

Time Complexity: O(n) for traversing both array.

Space Complexity: O(n) for the recursion stack.