Tree Topics

1. Traversals

  • DFS and Stack Based

    Example Code
     1def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
 2  def dfs(root):
 3    nonlocal result
 4    if not root:
 5      return
 6    result.append(root.val)
 7    dfs(root.left)
 8    dfs(root.right)
 9  
10  def iter(root):
11    nonlocal result
12    stack = [root] if root else []
13    while stack:
14      # stack top == current call stack
15      node = stack.pop()
16      result.append(node.val)
17
18      """ remmeber to push right first """
19      if node.right:
20        stack.append(node.right)
21      if node.left:
22        stack.append(node.left)
23
24def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
25  def dfs(root):
26    nonlocal result
27    if not root:
28      return
29    dfs(root.left)
30    result.append(root.val)
31    dfs(root.right)
32  
33  def push_left(stack, root):
34    while root:
35      stack.append(root)
36      root = root.left
37  
38  def iter(root):
39    nonlocal result
40    """
41    we need to simulate how the call stack works
42    (a) push as many left elements as possible as init
43    (b) popping means processing
44    (c) once we pop, we need to move right and then do (a) again
45    """
46    stack = []
47    """ NOTE we have to do this before entering the loop """
48    push_left(stack, root)
49
50    while stack:
51      node = stack.pop()
52      result.append(node.val)
53      push_left(stack, node.right)
54
55  result = []
56  iter(root)
57  return result
58
59# Definition for a binary tree node.
60# class TreeNode:
61#     def __init__(self, val=0, left=None, right=None):
62#         self.val = val
63#         self.left = left
64#         self.right = right
65class BSTIterator:
66
67  def __init__(self, root: Optional[TreeNode]):
68    self.stack = []
69    self.push_left(root)
70
71  def push_left(self, node):
72    while node:
73      self.stack.append(node)
74      node = node.left
75
76  def next(self) -> int:
77    top = self.stack.pop()
78    self.push_left(top.right)
79    return top.val
80
81  def hasNext(self) -> bool:
82    return len(self.stack) > 0
83
84
85# Your BSTIterator object will be instantiated and called as such:
86# obj = BSTIterator(root)
87# param_1 = obj.next()
88# param_2 = obj.hasNext()

2. Lowest Common Ancestor

  • Tree LCA variants

    Example Code
      1# binary tree
  2""" unique nodes, p, q guaranteed to exist in tree """
  3def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
  4  # three possible cases
  5  # if root = p and any of the subtrees contain q, then p is the lca
  6  # if root = q and any of the subtrees contain p, then q is the lca
  7  # if one of the subtrees contains p and the other contains q, then root is the lca
  8  def lca(root, p, q):
  9    if not root:
 10      return root
 11    # if any of the nodes are found first, they are returned
 12    # case 1: the other node is one of the subtrees - in this case, root is lca
 13    # case 2: the other node is in another part, then it would help upstream
 14    # level root to figure it out
 15    if root == p or root == q:
 16      return root
 17
 18    left = lca(root.left, p, q)
 19    right = lca(root.right, p, q)
 20
 21    if left is not None and right is not None:
 22      return root
 23    if left is not None:
 24      return left
 25    if right is not None:
 26      return right
 27    return None
 28  
 29  return lca(root, p, q)
 30
 31# binary search tree
 32""" unique nodes, p, q guaranteed to exist in tree """
 33def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
 34  def lca(root, p, q):
 35    # we can assume that p.val < q.val
 36    if not root:
 37      return root
 38    # here we effectively prune the search space using bst property
 39    if q.val < root.val:
 40      return lca(root.left, p, q)
 41    if root.val < p.val:
 42      return lca(root.right, p, q)
 43    # we can confidently return root if p.val < root.val < q.val
 44    # since it is guaranteed that the nodes are going to be present
 45    # in the binary search tree
 46    return root
 47  
 48  if p.val > q.val:
 49    p, q = q, p
 50  return lca(root, p, q)
 51
 52"""
 53Older code
 54# Binary tree structure
 55class TreeNode:
 56    def __init__(self, val=0, left=None, right=None):
 57        self.val = val
 58        self.left = left
 59        self.right = right
 60
 61class Solution:
 62    def lca1(self, root, p, q):
 63        if root is None:
 64            return root
 65        if root == p or root == q:
 66            return root
 67        left = self.lca1(root.left, p, q)
 68        right = self.lca1(root.right, p, q)
 69        if left is not None and right is not None:
 70            return root
 71        return left if left is not None else right
 72    def lca2(self, root, p, q):
 73        if root is None:
 74            return None
 75        if p is None and q is None:
 76            return None
 77        if root == p:
 78            if q is None:
 79                return root
 80            left = self.lca2(root.left, None, q)
 81            right = self.lca2(root.right, None, q)
 82            if left is not None or right is not None:
 83                return root
 84        elif root == q:
 85            if p is None:
 86                return root
 87            left = self.lca2(root.left, p, None)
 88            right = self.lca2(root.right, p, None)
 89            if left is not None or right is not None:
 90                return root
 91        else:
 92            left = self.lca2(root.left, p, q)
 93            right = self.lca2(root.right, p, q)
 94            if left is not None and right is not None:
 95                return root
 96        return None
 97
 98def test1():
 99    # Test Case
100    root = TreeNode(3)
101    root.left = TreeNode(5)
102    root.right = TreeNode(1)
103    root.left.left = TreeNode(6)
104    root.left.right = TreeNode(2)
105    root.right.left = TreeNode(0)
106    root.right.right = TreeNode(8)
107    root.left.right.left = TreeNode(7)
108    root.left.right.right = TreeNode(4)
109
110    # Nodes
111    p = root.left  # Node with value 5
112    q = root.right  # Node with value 1
113
114    # Expected Output: 3
115    return root, p, q
116
117def test2():
118    # Binary tree structure
119    root = TreeNode(3)
120    root.left = TreeNode(5)
121    root.right = TreeNode(1)
122    root.left.left = TreeNode(6)
123    root.left.right = TreeNode(2)
124
125    # Nodes
126    p = root.left  # Node with value 5
127    q = TreeNode(10)  # Node with value 10 (not present in the tree)
128
129    # Expected Output: None (as `q` is not in the tree)
130    return root, p, q
131
132def test3():
133    # Binary tree structure
134    root = TreeNode(3)
135    root.left = TreeNode(5)
136    root.right = TreeNode(5)
137    root.left.left = TreeNode(6)
138    root.left.right = TreeNode(2)
139
140    # Nodes
141    p = root.left  # Node with value 5 (left subtree)
142    q = root.right  # Node with value 5 (right subtree)
143
144    # Expected Output: 3
145    return root, p, q
146
147if __name__ == '__main__':
148    solution = Solution()
149    root, p, q = test1()
150    res = solution.lca2(root, p, q)
151    print(res.val)
152"""

3. Validation

  • Is valid BST

    Example Code
     1def isValidBST(self, root: Optional[TreeNode]) -> bool:
 2  def range(root, tree_min, tree_max) -> bool:
 3    if not root:
 4      return True
 5    
 6    if tree_min < root.val and root.val < tree_max:
 7      # root is valid, now check subtrees
 8      left_valid = range(root.left, tree_min, root.val)
 9      right_valid = range(root.right, root.val, tree_max)
10      if left_valid and right_valid:
11        return True
12    
13    return False
14
15  def minmax(root) -> Tuple[int,int]:
16    # returns min, max of the tree rooted at root
17    if not root:
18      # note that the order is kept like this
19      # so that any parent subtree is not invalidated because
20      # of empty children
21      return inf, -inf
22    
23    left_min, left_max = minmax(root.left)
24    right_min, right_max = minmax(root.right)
25
26    if left_max < root.val and root.val < right_min:
27      left_min = min(left_min, root.val)
28      right_max = max(right_max, root.val)
29      return left_min, right_max
30    
31    # if comes here, then all parent subtrees are invalidated
32    return -inf, inf
33  
34  # tree_min, tree_max = minmax(root)
35  # return tree_min > -inf and tree_max < inf
36
37  return range(root, -inf, inf)

  • Is valid preorder

    Example Code
     1def verifyPreorder(self, preorder: List[int]) -> bool:
 2  # the idea is to use a monotonic stack
 3  # to simulate call stack in a bst
 4  """
 5  IMPORTANT
 6  BST assumption for preorder is that once a node is processed
 7  all the left subtree nodes are also processed. So the only values
 8  we're allowed to process are larger than the node.
 9  """
10  stack = []
11  # all next values should be larger than this
12  min_limit = -inf
13  for curr in preorder:
14    while stack and stack[-1] < curr:
15      # updating the min_limit here because nothing that
16      # comes after should be smaller than this
17      min_limit = stack.pop()
18    if min_limit > curr:
19      return False
20    stack.append(curr)
21  return True

  • Serialize and Deserialize BST

    Example Code
     1# Definition for a binary tree node.
 2# class TreeNode:
 3#     def __init__(self, x):
 4#         self.val = x
 5#         self.left = None
 6#         self.right = None
 7
 8class Codec:
 9
10  def serialize(self, root: Optional[TreeNode]) -> str:
11    """Encodes a tree to a single string.
12    """
13    # note that just the preorder traversal is sufficient for serialization
14    preorder = self.iterative_preorder_traversal(root)
15    return ','.join([str(x) for x in preorder])
16
17  def deserialize(self, data: str) -> Optional[TreeNode]:
18    """Decodes your encoded data to tree.
19    """
20    if len(data) == 0:
21      return None
22
23    preorder = [int(x) for x in data.split(',')]
24    return self.construct_from_preorder(preorder)
25  
26  def construct_from_preorder(self, preorder: List[int]) -> Optional[TreeNode]:
27    assert(len(preorder) > 0)
28
29    # root needs special attention as it has to be returned
30    root = TreeNode(preorder[0])
31    max_stack = [root]
32
33    for index in range(1, len(preorder)):
34      node = TreeNode(preorder[index])
35
36      last_popped = None
37      while max_stack and max_stack[-1].val < node.val:
38        last_popped = max_stack.pop()
39
40      if last_popped is not None:
41        last_popped.right = node
42      elif max_stack:
43        max_stack[-1].left = node
44
45      max_stack.append(node)
46    
47    return root
48
49  def iterative_preorder_traversal(self, root: Optional[TreeNode]) -> List[int]:
50    preorder = []
51
52    stack = [root] if root else []
53    while stack:
54      node = stack.pop()
55      preorder.append(node.val)
56      if node.right:
57        stack.append(node.right)
58      if node.left:
59        stack.append(node.left)
60    
61    return preorder
62
63# Your Codec object will be instantiated and called as such:
64# Your Codec object will be instantiated and called as such:
65# ser = Codec()
66# deser = Codec()
67# tree = ser.serialize(root)
68# ans = deser.deserialize(tree)
69# return ans

3. Segment Tree

  • Basics - Sum queries - Update queries - Memory efficient implementation

  • Advanced Topics - Finding the maximum - Finding the maximum and the number of times it appears - Compute the greatest common divisor / least common multiple - Counting the number of zeros, searching for the $k$ -th zero - Searching for an array prefix with a given amount - Searching for the first element greater than a given amount - Finding subsegments with the maximal sum

  • Saving the entire subarrays in each vertex - Find the smallest number greater or equal to a specified number. No modification queries. - Find the smallest number greater or equal to a specified number. With modification queries. - Find the smallest number greater or equal to a specified number. Acceleration with “fractional cascading”.

  • Range updates (Lazy Propagation) - Addition on segments - Assignment on segments - Adding on segments, querying for maximum

  • Generalization to higher dimensions - Simple 2D Segment Tree - Compression of 2D Segment Tree

  • Preserving the history of its values (Persistent Segment Tree) - Finding the $k$ -th smallest number in a range

  • Dynamic segment tree