Tree

Definitions

The upgraded version of a linked list.

It is acyclic (doesn’t contain any cycles);
There exists a path from the root to any node;
Has \(N - 1\) edges, where \(N\) is the number of nodes in the tree; and
Each node has exactly one parent node with the exception of the root node.

For binary tree, all nodes have at most 2 children.

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Terms	Meaning
Node & Edges	Trivia
Root	The first node
Leaf node	Node with no child
Internal node	Node with at least one child
Ancestor	Nodes that are between the path from the root to the current root. Including the node itself
Descendent	Nodes that are between the path from the root to the current root. Including the node itself
Level	Number of ancestors from that node until the root node. Start at 0 or 1, go down.
Height	Number of edges on the longest path from that node to a leaf. Start at 0, go up.
Depth	Number of edges on the path from root to that node. Start at 0, go down.

Notes:

1. Breadth-first search

Breadth-first search is first heavily used technique. Here’s the template adapted from LeetCode Explore:

from collections import deque

def BFS(root, target):
    queue = deque() # store all nodes which are waiting to be processed
    visited = set() # store all the nodes that we've visited
    step = 0 # number of steps needed from root to current node
    # initialize
    queue.append(root)
    visited.add(root)
    # BFS
    while queue:
        # iterate the nodes which are already in the queue
        size = len(queue)
        for i in range(size):
            cur = queue.popleft()
            if cur == target:
                return step
            for next in cur.neighbors:
                if next not in visited:
                    queue.append(next)
                    visited.add(next)
        step += 1
    return -1 # there is no path from root to target

This template uses a set to track the node visited. In a graph, as a cycle is possible, this is necessary. However, because a tree is acyclic, it is not necessary

from collections import deque

def BFS(root, target):
    queue = deque() # store all nodes which are waiting to be processed
    # visited = set() # store all the nodes that we've visited
    step = 0 # number of steps needed from root to current node
    # initialize
    queue.append(root)
    # visited.add(root)
    # BFS
    while queue:
        # iterate the nodes which are already in the queue
        size = len(queue)
        for i in range(size):
            cur = queue.popleft()
            if cur == target:
                return step
            if cur.left:
                queue.append(cur.left)
            if cur.right:
                queue.append(cur.right)
        step += 1
    return -1 # there is no path from root to target

2. Depth-first search

Depth-first search is the second heavily used technique. It is essentially pre-order traversal of a tree. All traversal types are given here:

from typing import Optional, List

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

   def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # Edge case
        if not root:
            return []

        # General case
        result, stack = [], [root]
        while stack:
            node = stack.pop()
            result.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return result

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result, stack = [], []
        current = root
        
        while current or stack:
            while current:
                stack.append(current)
                current = current.left
            
            current = stack.pop()
            result.append(current.val)
            current = current.right
        
        return result
    
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # Edge case
        if not root:
            return []
        
        # Approach 1
        result, stack = [], [root]
        while stack:
            node = stack.pop()
            result.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return result[::-1]

        # Approach 2
        result, stack = [], [root]
        visited = [False]

        while stack:
            current, visit_already = stack.pop(), visited.pop()
            if visit_already:
                result.append(current.val)
            else:
                stack.append(current)
                visited.append(True)
                stack.append(current.right)
                visit.append(False)
                stack.append(current.left)
                visit.append(False)
        
        return result

Here’s the template from AlgoMonster:

def dfs(root, target):
    if root is None:
        return None

    if root.val == target:
        return root
    left = dfs(root.left, target)

    if left is not None:
        return left
    return dfs(root.right, target)

Depth-first search is often implemented in recursion (you can go hardcore and implement it with a stack as above).

3. Recursion

In thinking in recursion, one must forget the whole picture and start thinking about each node. There are two ways to implement recursive depth-first search in tree: top-down and bottom-up, a.k.a from root to leaves or from leaves to root.

In the top-down approach, check if the children’s answer can be figured out knowing the value and answer of the root. That means checking for ways to update the answer, and checking if the implementation is good, or at least better than in bottom up.

In the bottom-up approach, check if the children’s answer can be used to update the node’s answer. The criteria are as above.

There are problems where one approach makes more sense than the other in terms of runtime and/or memory. But always check both.

Bottom-up seems more intuitive to me.

I care about the two variables:

return value - the value the child passes to the parent. For example, for the max depth problem this is the max depth for the current node’s subtree.
state - the value the parent passes to the child. For example, to know if the current node’s value is larger than its parent we have to maintain the parent’s value as a state.

Another way to implement is to replace the return value with a nonlocal variable. This is usually coupled with using a nested function. This makes the code hard to read and hard to debug so avoid.

Problems

1. Flatten Binary Tree to Linked List

Intuition

Depth-first search is recursion. The problem is constructing a repeatable sequence that can lead to the final result. The hint was “it looks like pre-order traversal”. It was about traversing to the left child first after the current node. But the key sequence is from the root, attaching the right child to the rightmost node in the left subtree, and move the left child i.e., the root of the left subtree to the right. And then move on to the right child, formerly the left child.

Algorithm

Traverse the binary tree, check the existsnce of the left child of the current node.
If the left child exists, find the rightmost node in the left subtree.
Set the right child of the current node as the right child of the rightmost node above.
Set the left child of the current node as its right child.
Set the left child of the current node as None.
Move to the right child

Complexity

Time complexity: \(O(n)\): Iterate the binary tree.
Space complexity: \(O(1)\): The tree is modified in-place.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        # Edge case
        if not root:
            return
        
        # General case
        current = root
        while current:
            if current.left:
                last = current.left
                
                while last.right:
                    last = last.right
                
                last.right = current.right
                current.right = current.left
                current.left = None
            
            current = current.right

2. Binary Tree Level Order Traversal

Intuition

The question asks you and me to implement breadth-first search. So let’s do it.

Algorithm

Initialize a queue to store all nodes of each level, start with root.
Take the current level_length and operates on the queue for level_length time:
1. Pop from the left of the queue and add the value to a list for the level.
2. Add the children to the queue.
Add the list of values of each level to the return list.
Return.

Complexity

Time complexity: \(O(n)\): Iterate the binary tree.
Space complexity: \(O(n)\): The size of the queue is n // 2 in the worst case.

Code

from typing import (
    List,
)
from lintcode import (
    TreeNode,
)
from collections import deque
"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: A Tree
    @return: Level order a list of lists of integer
    """
    def level_order(self, root: TreeNode) -> List[List[int]]:
        # write your code here
        # Edge case
        if not root:
            return []
        
        # General case
        queue = deque()
        result = []
        queue.append(root)

        while queue:
            level = []
            level_length = len(queue)
            for _ in range(level_length):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)
        return result

3. Binary Tree Zigzag Level Order Traversal

Intuition

Sounds like Level order traversal plus reversing the level-wise traversal every two levels. One incorecct answer is reversing the order of appending children nodes to the levelwise traversal but it is wrong as it does not fully reverse the order of traversal.

A better solution is using a double-ended queue i.e., deque. This one supports appendleft(), so if the current level should be reversed, the operations can be switched from popleft() then append() to pop then appendleft().

Algorithm

Perform level order traversal. Reverse the levelwise traversal every two levels.
Return the traversal.

Complexity

Time complexity: \(O(n)\): Some level is effectively traversed twice, but the overall is still \(O(n)\)
Space complexity: \(O(n)\): THe size of the queue.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # Edge case
        if not root:
            return []
        
        # General case
        queue = deque([root])
        level = 1
        zigzag_traversal = []
        while queue:
            level_traversal = []
            level_length = len(queue)

            if level % 2:
                for _ in range(level_length):
                    node = queue.popleft()
                    level_traversal.append(node.val)

                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
            else:
                for _ in range(level_length):
                    node = queue.pop()
                    level_traversal.append(node.val)

                    if node.right:
                        queue.appendleft(node.right)
                    if node.left:
                        queue.appendleft(node.left)
                    
            if level % 2:
                level_traversal = level_traversal[::-1]
            zigzag_traversal.append(level_traversal)
            level += 1
        return zigzag_traversal

4. Populating Next Right Pointers in Each Node

Intuition

Breadth-first search makes the most sense in this problem. However, the question is how to do the problem in \(O(1)\) extra memory. That means using only pointers and do away with the queue. How?

I remember from the introduction that the purpose of the next pointer is to do away with the queue in level order traversal. And the (only) way I connect them is connecting the child level of a node i.e., pointing the left child to the right child. This means that when I arrive at a level, all the nodes should already be connected and I can just traverse with next pointer. And as said above, connecting the left child of a node to the right child is trivial. To connect the right child of a node the next left child, I need to use the next pointer of the current node. Implementation was straightforward, but coming up with the concept is crazy.

Algorithm

Initialize a pointer pointing to the current node and a pointer pointing to the first node of a level.
Traverse the current level, connecting the node of the next level.
Once having reached the end, move to the next level and update pointers.
Return at the end.

Complexity

Time complexity: \(O(n)\): Traverse every node in the tree.
Space complexity: \(O(1)\): Only use pointers to connect new nodes together.

Code

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        current_node, start_next_level = root, root.left if root else None

        while current_node and start_next_level:
            current_node.left.next = current_node.right
            if current_node.next:
                current_node.right.next = current_node.next.left
            
            current_node = current_node.next
            if not current_node:
                current_node = start_next_level
                start_next_level = current_node.left
        
        return root

5. Vertical Order Traversal of a Binary Tree

Intuition

Breadth-first search will guaranteed that nodes at the top i.e., at higher row will be visited first. The column can become the key to store the list of node values in a HashMap. These were my immediate sketches.

The problem specifies that the values should be sorted by row, and then by value. This means that I need to be able to access the position values of a node at each iteration. That means that I need to store the row and column of a node in the queue when I enqueue the node.

It’s amazing - I used to doubt if I can come up with a chain of thought such as this. Now at some moment I can. Maybe this is the meaning of growth.

Algorithm

Initialize the queue with the root node, row, and column all in one tuple + the HashMap to map column to list of values.
Traverse the tree with breadth-first search. For each element in the current level:
1. Add the current node value and row to the corresponding list (using the column as the key) in the HashMap.
2. Add the left child and right child together with its respective position to the queue.
Sort the keys of the HashMap.
Access each list of values in the HashMap, sort the list according to the row and then the node value.
Return the final list.

Complexity

Time complexity: \(O(n \log n)\): The dominating operation is sorting of columns. The number of different columns is as many as the number of leaf nodes, which can reach \(\lfloor n/2 \rfloor\) in a perfect binary tree.
Space complexity: \(O(n)\): In a perfect binary tree, the queue will need to hold \(\lfloor n/2 \rfloor\) elements.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque, defaultdict
from typing import Optional, List

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        queue = deque([(root, 0, 0)])
        position_map = defaultdict(list)

        while queue:
            level_length = len(queue)
            for _ in range(level_length):
                node, row, column = queue.popleft()
                position_map[column].append((node.val, row))
                if node.left:
                    queue.append((node.left, row + 1, column - 1))
                if node.right:
                    queue.append((node.right, row + 1, column + 1))
        
        result = []
        all_columns = list(position_map.keys())
        all_columns.sort()
        for column in all_columns:
            column_values = position_map[column]
            column_values.sort(key = lambda x:(x[1], x[0]))
            result.append([value[0] for value in column_values])
        
        return result

5. Maximum Depth of Binary Tree

Intuition

The introductory problem in depth-first search and thinking in recursion. The most intuitive way is bottom-up: the depth of a leaf is 0 as I am counting from the leaf, and the depth of a node is 1 plus the maximum depth of its child(ren). You can certainly do this in a top-down manner: the depth of 0 now is for the root, and the depth of each child is the depth of its parent plus 1. In the end, both return the maximum depth.

Algorithm

For bottom-up:

Define the base case: return 0 for a null node and the terminal case: return 1 plus the larger depth between the two children.
Call the function recursively on the left and right subtrees of each node and get the answer.
Return the final answer.

For top-down:

For this one, a helper function is better, with the current depth also passed in as a parameter. Again, define the base case: return the depth passed in as is for null nodes, and the terminal case: the maximum depth of the two substrees.
Call the function recursively on the left and right subtrees of each node and get the answer.
Return the final answer.

Complexity

Time complexity: \(O(n)\): Visit every node once.
Memory complexity: \(O(1)\): Both cases only store some integers.

Code

Bottom-up

from lintcode import (
    TreeNode,
)

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: The root of binary tree.
    @return: An integer
    """
    def max_depth(self, root: TreeNode) -> int:
        # write your code here
        if not root:
            return 0

        left_depth = self.max_depth(root.left)
        right_depth = self.max_depth(root.right)

        return 1 + max(left_depth, right_depth)

Top-down

from lintcode import (
    TreeNode,
)

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: The root of binary tree.
    @return: An integer
    """
    def max_depth(self, root: TreeNode) -> int:
        # write your code here
        return self._max_depth(root, 0)

    def _max_depth(self, root: TreeNode, depth: int) -> int:
        if not root:
            return depth
        
        left_depth = self._max_depth(root.left, depth + 1)
        right_depth = self._max_depth(root.right, depth + 1)

        return max(left_depth, right_depth)

6. Symmetric Tree

Intuition

I thought of this in a top-down manner. The symmetry can be checked by going down the level, start with the left and right children of root. The conditions for symmetric are:

The two nodes having the same value.
The alternating children having the same value.

and then going down to the leaves.

One note on implementation. The most important aspects of coding interview is not getting the optimal solution. It is also not just explaining your solution. You can use a sub-optimal solution that passes the test cases if your coding quality is good. Good code quality means:

Spacing: Add one space after unary operators and on both sides of binary operators such as =. Add one space after comma. Add one blank line between different logical blocks.
Naming: Descriptive names for functions and variables. Limit to 1-2 words.
Indentation: No more than 3 levels. Use less if statements. The moment you become tired of the number of if statements you have to put in, that means this is the wrong direction.
Separateness: Use more subfunctions to reduce the codes in the entry function.
Exception handling: Always check for exceptions of the entry parameters. Check if an object is null when access. Make sure the index of an array is not out of bound. Do not use global variable.

In the recursion problem, this means “redundant” function calls and assignments to two variables before return.

The problem can be solved iteratively using DFS or BFS. In DFS, it is checking the preorder traversal of the tree is the same as the preorder traversal of the reversed tree. In BFS, it is checking whether each level is a palindrome. The solutions are included.

Algorithm

Top-down recursion. Define the base case: return True if both nodes are null, and False is only one nodes are null and the terminal case: the values of two nodes and alternating children are the same.
Call the function and return the result.

Complexity

Time complexity: \(O(n)\): Each node is visited once.
Space complexity: \(O(n)\): This is the size of the recursive call stack, which momentarily stores all nodes of the tree.

Code

Recursion

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.isEqual(root.left, root.right)

    def isEqual(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        if not root1 and not root2:
            return True
        if not root1 or not root2:
            return False
        
        left_result = self.isEqual(root1.left, root2.right)
        right_result = self.isEqual(root2.left, root1.right)

        return root1.val == root2.val and left_result and right_result

Iterative DFS

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
import collections
class Solution:
    """
    @param root: root of the given tree
    @return: whether it is a mirror of itself 
    """
    def isSymmetric(self, root):
        order = self.preorder(root, reverse=False)
        reverse_order = self.preorder(root, reverse=True)
        return order == reverse_order

    def get_left(self, node: TreeNode, reverse: bool):
        if reverse:
            return node.right
        return node.left

    def get_right(self, node: TreeNode, reverse: bool):
        if reverse:
            return node.left
        return node.right

    def preorder(self, root: TreeNode, reverse: bool):
        order = []
        if not root:
            return order
        stack = collections.deque([])
        stack.append(root)
        while stack:
            node = stack.popleft()
            if node == "#":
                order.append("#")
                continue
            else:
                order.append(node.val)
            
            left = self.get_left(node, reverse)
            if left:
                stack.append(left)
            else:
                stack.append("#")
            
            right = self.get_right(node, reverse)
            if right:
                stack.append(right)
            else:
                stack.append("#")
        return order

BFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        queue = deque([root])
        while queue:
            if not self.isMirror(queue):
                return False
            for i in range(len(queue)):
                node = queue.popleft()
                if not node:
                    continue
                queue.append(node.left)
                queue.append(node.right)
        return True
    
    def isMirror(self, queue: deque) -> bool:
        left, right = 0, len(queue) - 1
        while left < right:
            if not self.isSame(queue[left], queue[right]):
                return False
            left += 1
            right -= 1
        return True

    def isSame(self, node1: Optional[TreeNode], node2: Optional[TreeNode]) -> bool:
        if node1 and node2:
            return node1.val == node2.val
        return node1 is None and node2 is None

7. Path Sum

Intuition

Top-down recursion. I want to propagate the sum down the tree, and only check for condition at the leaves. This means that the current sum needs to be passed down as state of the previous level, and whether the current sum up to a leaf equals the target sum is the return of the function. An implementation issue is updating the return boolean value, as one path sum is enough to declare True, but I need to check up to the last path if all previous are False. This means the return value needs passing in as a parameter.

Algorithm

Top-down recursion. Define the base case: return result or curSum == targetSum if the node is a leaf node. Otherwise, move to the left child and/or right child if exist.
Return the updated result

Incredibly simple, yet hard to think up.

Complexity

Time complexity: \(O(n)\): At worst, visit every node in the tree.
Space complexity: \(O(n)\) - \(\Omega (\log n)\): The recursive call stack stores one path at a time, which corresponds to the height of the tree. At worst, \(n\), at best, \(\log n\)

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        # Edge case
        if not root:
            return False
        
        return self._hasPathSum(root, root.val, targetSum, False)
                               
    def _hasPathSum(self, root: Optional[TreeNode], curSum: int, targetSum: int, result: bool) -> None:

        if not (root.left or root.right):
            result = result or curSum == targetSum
            return result
        
        if root.left:
            result = self._hasPathSum(root.left, curSum + root.left.val, targetSum, result)
        if root.right:
            result = self._hasPathSum(root.right, curSum + root.right.val, targetSum, result)

        return result

NeetCode’s solution

class Solution:
    def hasPathSum(self, root, sum):
        if not root:
            return False
        de = [
            (root, sum - root.val),
        ]
        while de:
            node, curr_sum = de.pop()
            if not node.left and not node.right and curr_sum == 0:
                return True
            if node.right:
                de.append((node.right, curr_sum - node.right.val))
            if node.left:
                de.append((node.left, curr_sum - node.left.val))
        return False

8. Construct Binary Tree from Inorder and Postorder Traversal

Intuition

I noticed that the last value of the postorder traversal list must be the root, based on how the operation is defined. Hence, I know the root. I then noticed that the root will appear somewhere in the middle of the inorder traversal list, which can be used to separate the inorder traversal list: the left part will be the left subtree, the right part will be the right subtree. Interestingly enough, if the left subtree has \(n\) elements, in the inorder or the postorder traversal, the left subtree will cover the exact same first \(n\) elements. And here it gets interesting: the last value of the left subtree postorder traversal will be th root, which can be found in the middle of the corresponding inorder traversal, which can be used to separate the nodes into the left and right subtrees again! I have found a recursive a la fractal pattern.

My first solution works, but it was slow and consumed too much memory. That was because the runtime complexity is \(O(n^2)\) - in every call I perform a linear scan on the inorder traversal array to find the root. Worse, I created new subarrays with slicing on every call, making the memory inefficient. Although I might have still secured the job interview with the code quality, I reckon that I will have been pushed to a better solution. NeetCode proposed two things:

The indices are enough to slice the array. So pass indices between recursive calls instead of slicing the arrays. This is retrospectively obvious given the definition of array. It is also useful. In fact, I now realize how to pass the OA from TikTok that I dreadfully failed because of memory inefficiency.
Use dictionary for repeated search. The memory is still \(O(n)\), but it saves \(O(n)\) for the runtime complexity.

Another note on implementation: the right subtree must be constructed first, according to the order of the postorder traversal. I attempted to construct the left subtree first, which leads to error.

Algorithm

Initialize the hash map to map values to indices.
Define the helper function. Normally, I would condemn the practice of nested function but in this case it is justified as otherwise I will need to pass in the dictionary to the hidden method, incurring \(O(n^2)\) memory.
1. The root has the value as last value of postorder traversal, which is popped from the array.
2. The right and left children are constructed sequentially from recursive calls.
3. The two pointers to the position on the inorder traversal array are used as safeguards to return when conditions are met.
Return the tree.

Complexity

Time complexity: \(O(n)\): Visit every node in the tree.
Memory complexity: \(O(n)\): The maximum size of the recursive call stack and the size of the hash map.

Code

Initial

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # Base case
        if len(inorder) == 1:
            return TreeNode(inorder[-1])
        if len(inorder) == 0:
            return 
        
        # General case
        root = postorder[-1]
        root_index = inorder.index(root)
        left_inorder, right_inorder = inorder[:root_index], inorder[root_index + 1:]
        left_postorder, right_postorder = postorder[:root_index], postorder[root_index:-1]
        return TreeNode(root,
                        self.buildTree(left_inorder, left_postorder),
                        self.buildTree(right_inorder, right_postorder))

Optimized

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        inorderIdx = {value:index for index, value in enumerate(inorder)}
    
        def _buildTree(left, right):
            # Base case
            if not postorder or left > right:
                return
        
            # General case
            root = TreeNode(postorder.pop())
        
            root_index = inorderIdx[root.val]
            
            root.right = _buildTree(root_index + 1, right)
            root.left = _buildTree(left, root_index - 1)
            return root
        
        return _buildTree(0, len(inorder) - 1)

8. Construct Binary Tree from Inorder and Postorder Traversal

Intuition

A similar problem. I can’t help noticing these two problems seem to be the cue for Serialize and Deserialize Binary Tree. It is signaling that we need at least two traversals of a tree to construct it?

Anyway, for this problem, the first element of inorder is the always the root. Cool. But the sticky issue arises: Python list cannot be popped from the front, so I have to make a new queue if I want to follow the lead of the previous problem. The other choice is to pass in more pointers - now the pointers for both preorder and inorder need passing in.

Algorithm

Initialize the hash map to map values to indices.
Define the helper function. Parameters are 4 pointers corresponding to the start and end of both arrays.
1. The root has the value as first value of preorder traversal.
2. The size of the left subtree is calculated from the index of inorder root and inorder left. Note here: to guarantee correct access, inorder left has to be incremented at every call. Thus, the size of the left subtree is necessary to calculate the correct right pointer for preorder traversal.
3. The right and left children are constructed sequentially from recursive calls.
4. The two pointers on prenorder traversal array are used as safeguards to return when conditions are met.
Return the tree.

Complexity

Time complexity: \(O(n)\): Visit every node in the tree.
Memory complexity: \(O(n)\): The maximum size of the recursive call stack and the size of the hash map.

Code

Initial

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
        if not preorder:
            return None
        
        root = TreeNode(preorder[0])
        mid = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:mid+1], inorder[:mid])
        root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])
        return root

Optimized

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # inorderIdx = dict(map(reversed, enumerate(inorder)))
        inorderIdx = {value: index for index, value in enumerate(inorder)}
        
        def _buildTree(preorder_left, preorder_right, inorder_left, inorder_right):
            if preorder_left > preorder_right:
                return
            
            # Preorder root is always the preorder left a la the first element
            root = TreeNode(preorder[preorder_left])
            inorder_root = inorderIdx[root.val]
            size_left_subtree = inorder_root - inorder_left
            # left_inorder, right_inorder = inorder[:root_index], inorder[root_index + 1:]
            # left_preorder, right_preorder = preorder[1:root_index+1], preorder[root_index + 1:]

            root.left = _buildTree(preorder_left + 1, preorder_left + size_left_subtree,
                                    inorder_left, inorder_root - 1)
            root.right = _buildTree(preorder_left + size_left_subtree + 1, preorder_right,
                                    inorder_root + 1, inorder_right)
            return root

        return _buildTree(0, len(preorder) - 1, 0, len(inorder) - 1)

9. Populating Next Right Pointers in Each Node II

Intuition

I was thinking of how to extend from the first problem. I came up with a super convoluted attempt, only to realize that, hey, if the supposed next node is super far, I am dead. The solution is returning to the most simple one: breadth-first traversal. Okay, cool. But how can I make it \(O(1)\) space?

The trick turns out to go back to a data structure that also has .val and .next: Linked List. Yes, it is the dummy head trick. Each level will be treated as a linked list to be connected together, with a dummy node serving as the temporary head.

Algorithm

Initialize dummy and head pointer.
For each level:
1. First, point current to head, and prev to dummy.
2. Traverse the level, connecting each node in a manner quite similar to reverse linked list.
Return the root.

Complexity

Time complexity: \(O(n)\): Visit every node in the array.
Space complexity: \(O(1)\): Only store pointers.

Code

Note that the solution is also applicable to the first problem in the series.

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        # Edge case
        if not root:
            return
        
        # General case
        head = root
        dummy = Node(-1)
        while head:
            current, prev = head, dummy
            while current:
                if current.left:
                    prev.next = current.left
                    prev = prev.next
                if current.right:
                    prev.next = current.right
                    prev = prev.next
                current = current.next
            head = dummy.next
            dummy.next = None
        return root

10. Lowest Common Ancestor of a Binary Search Tree

Intuition

Binary search tree is a special kind of binary tree, where every element in the left subtree is guaranteed to be smaller than the root, and every element in the right subtree is guaranteed to be larger than the root. Because of this problem, it is easy to see that the lowest common ancestor of two nodes will be the first node that is larger than the smaller node and smaller than the larger node.

Algorithm

Initialize: temp to root, small and large to corresponding nodes.
Traverse the tree with temp:
1. If temp is larger than large, go left.
2. If temp is smaller than small, go right.
3. Otherwise, return temp.

Complexity

Time complexity: \(O(\log n)\): I will need to traverse every level in the worst case.
Space complexity: \(O(1)\): I only need to store pointers’ values.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        temp = root
        small = p if p.val < q.val else q
        large = p if p != small else q
        while temp:
            if temp.val > large.val:
                temp = temp.left
            elif temp.val < small.val:
                temp = temp.right
            else:
                return temp

11. Serialize and Deserialize Binary Tree

Intuition

I was thinking about the two problems above of constructing binary tree from preorder and inorder traversals. However, this approach has two weaknesses:

It assumes that the node values are unique.
It is more complicated than necessary.

My first thought is actually more intuitive: breadth-first search a.k.a constructing the binary tree layer by layer. However, I can’t seem to be able to find a way to deserialize it properly. It turns out that the solution uses depth-first search - pre-order traversal to be specific.

Algorithm

Serialize: 1. Construct a string with preorder traversal, this time passing in an 'N' for null nodes. The nodes in the final string are separated with a comma.

Deserialize: 1. Split the string into an array. 2. Construct the tree, 1. The root of a tree (or subtree) is always the first element in the array. 2. When the value to construct a node is 'N', the node is constructed as null. This has the neat property that the children can always be constructed correctly in the recursive function simply by cosntructing the left subtree first (and use nonlocal keyword).

Complexity

Time complexity: \(O(n)\): Same for both methods: visit every node once.
Space complexity: \(O(n)\): Same for both methods: a new string/array containgin every node must be constructed.

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
# A better choice is breadth-first search
class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        result = []

        def preorderTraversal(node):
            if not node:
                result.append('N')
                return
            result.append(str(node.val))
            preorderTraversal(node.left)
            preorderTraversal(node.right)

        preorderTraversal(root)
        return ','.join(result)
        
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        data = data.split(',')
        _index = 0

        def buildTree():
            nonlocal _index
            if data[_index] == 'N':
                _index += 1
                return
            
            node = TreeNode(int(data[_index]))
            _index += 1
            node.left = buildTree()
            node.right = buildTree()
            return node
        
        return buildTree()

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

12. Invert Binary Tree

Intuition

Trivial problem. It is essentially swapping the place of the left and right children, and call the function recursively down the tree. This can be top-down or bottom-up, but the change is so trivial as to change the position of a line of code.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return
        
        self.invertTree(root.left)
        self.invertTree(root.right)
        root.left, root.right = root.right, root.left
        return root

13. Same Tree

Intuition

This is another trivial problem. However, it can become the building block for other interesting problems.

In recursion, it is as simple as checking whether the two node values are equal, and then check recursively for the left and right subtrees.

Code

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p or not q:
            return not p and not q
            
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

14. Subtree of Another Tree

Intuition

Subtree of Another Tree… means that the tree from subRoot is equal to a subtree in root. The problem of Same Tree thus provides the hint to solving this question.

However, the interesting does not stop here. The same tree, by definition, will have the same serialization, which bears itself to the problem of serialization and deserialization of a binary tree above. And this gives rise to another approach: serialization of trees to strings, and then use string matching solution to find it.

Let’s explore each in details.

“Same Tree”-inspired Recursion

Intuition

The method .isSameTree() is defined again here and is called at each iteration of the .isSubtree() method to check the current root and sub-root. Note that .isSubtree() calls itself, not .isSameTree() recursively.

Complexity

Define:

\(m\): Number of nodes in subRoot tree.

\(n\): Number of nodes in root tree.

Time complexity: \(O(mn)\) - For each of \(n\) nodes in root tree, check whether that node is the root of a tree same as subRoot tree. Each check will take \(O(m)\) operations. That looked terrible, but I then realized that in most of the case it will only take \(O(1)\) operation as the root values are different. Plus, there is no avoiding iterating throught the whole root tree.
Space complexity: \(O(m+n)\) - At most \(O(n)\) recursive calls to .isSubtree(), with \(O(m)\) more recursive calls to .isSameTree() on top of this.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not root:
            return False
        
        if self.isSameTree(root, subRoot):
            return True

        return (self.isSubtree(root.left, subRoot) or 
                self.isSubtree(root.right, subRoot))
         
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p or not q:
            return not p and not q
        return (p.val == q.val and
                self.isSameTree(p.left, q.left) and
                self.isSameTree(p.right, q.right))

String matching

Intuition

This solution consists of two steps: correctly serialize the tree, and then use a pattern matching algorithm (naive, Knuth-Morris-Pratt, Robin-Karp, etc.) to solve.

I have no intention of learning KMP. Besides, a good implementation of naive, or, at max, Robin-Karp, is enough to pass an interview.

Complexity:

Time complexity: \(O(mn) \text{ to } O(m+n)\) - Rabin-Karp algorithm requires iterating through each string once.
Space complexity: \(O(m)\) for both solutions.

Code

\(O(mn)\) best practice

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def serialize(node):
            serialization, stack = [], [node]

            while stack:
                node = stack.pop()
                if node:
                    serialization.append(str(node.val))
                    stack.append(node.right)
                    stack.append(node.left)
                else:
                    serialization.append('#')
            return serialization
        
        def string_match(source, target):
            if source is None or target is None:
                return False
            
            for i in range(len(source) - len(target) + 1):
                for j in range(len(target)):
                    if source[i + j] != target[j]:
                        break
                else:
                    return True
            
            return False
        
        root_series = serialize(root)
        subRoot_series = serialize(subRoot)

        return string_match(root_series, subRoot_series)

Rabin-Karp algorithm

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from typing import Optional, List

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        root_series = self.serialize(root)
        subRoot_series = self.serialize(subRoot)

        return self.stringMatch(root_series, subRoot_series)
    
    def serialize(self, node: Optional[TreeNode]) -> List[int]:
            serialization, stack = [], [node]

            while stack:
                node = stack.pop()
                if node:
                    serialization.append(node.val)
                    stack.append(node.right)
                    stack.append(node.left)
                else:
                    serialization.append('#')
            return serialization
    
    def computeHash(self, serialization: List[int], base: int = 13, prime_factor: int = 10**9 + 7) -> int:
        window_size = len(serialization)
        highest_value = pow(base, window_size - 1)
        
        current_hash = 0
        for element in serialization:
            element_value = element if element != '#' else (10**4 + 1)
            current_hash = (current_hash * base + element_value) % prime_factor
        return current_hash

    def stringMatch(self, source: List[int], target: List[int], base: int = 13, prime_factor: int = 10**9 + 7) -> bool:
        window_size = len(target)
        source_hash = self.computeHash(source[:window_size])
        target_hash = self.computeHash(target)
        if source_hash == target_hash:
            return True
        
        highest_value = pow(base, window_size - 1)
        for i in range(window_size, len(source)):
            removed_val = source[i - window_size] if source[i - window_size] != '#' else (10**4 + 1)
            source_hash = (source_hash - highest_value * removed_val) % prime_factor
            element_val = source[i] if source[i] != '#' else (10**4 + 1)
            source_hash = (base * source_hash + element_val) % prime_factor
            if source_hash == target_hash:
                return True
        return False

15. Balanced Binary Tree

Intuition

A balanced binary tree has no node with difference in height larger than 1. This means that I can get the height at each node, calculate the difference between children at a node, check and return. But my first attempt is a naive approach. Constructing the height of each node is bottom-up while checking for balancedness is top-down. The result is repetitive computation at \(O(n^2)\) time complexity.

To solve this efficiently, I need to check for balancedness right after calculating the height of children. The trick is to do so only if the tree is still balanced. Else, return a dummy value (-1 in this case) to end recursion. The result is \(O(n)\) time complexity.

Algorithm

For the helper method 1. If node is None, return 0 as the height (base case). 2. Call the helper method on the left and then right child. For the case: 1. If the left child is not balanced i.e. has a height of -1, return -1 immediately. 2. If the left child is balanced but the right child is not, also return -1. 3. If both children have non-minus-1 height but the absolute difference exceeds 1, return -1. 3. Return the maximum child height plus + 1 to account for the node.

Complexity

Time complexity: \(O(n)\) - Iterate through every node.
Space complexity: \(O(n)\) - The size of the recursion call stack.

Code

Naive solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from typing import Optional
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        left_balanced = self.isBalanced(root.left)
        right_balanced = self.isBalanced(root.right)
        return abs(self.getHeight(root.left) - self.getHeight(root.right)) < 2 and left_balanced and right_balanced

    def getHeight(self, node: Optional[TreeNode]) -> int:
        if not node:
            return 0
        return 1 + max(self.getHeight(node.left), self.getHeight(node.right))

Efficient solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from typing import Optional
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        return self._isBalanced(root) != -1

    def _isBalanced(self, node: Optional[TreeNode]) -> int:
        if not node:
            return 0
        left_height = self._isBalanced(node.left)
        if left_height == -1:
            return -1
        right_height = self._isBalanced(node.right)
        if right_height == -1:
            return -1
        if abs(left_height - right_height) > 1:
            return -1
        return 1 + max(left_height, right_height)

16. Diameter of Binary Tree

Intuition

In the easy case, the diameter can be calculated as the sum of heights of the children plus 2. That will make a nice recursive call to the root. But life is not like that - there may be a child with a larger diameter than the root.

To account for this, well, I will just make it a return value for the recursive method as well.

Algorithm

For the helper recursive function 1. Base case: if a node is None, its height and diameter will both be -1. 2. Recursive case: the height is calculated as before, but the diameter will be the maximum between the diameter of the left child, the diameter of the right child, and the local diameter i.e., 2 plus sum of the children heights.

Complexity

Time complexity: \(O(n)\) - bottom-up recursion, iterate through each node once.
Space complexity: \(O(n)\) - the size of the recursive call stack.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        return self.getDiameterAndHeight(root)[0]
        
    def getDiameterAndHeight(self, node: Optional[TreeNode]) -> int:
        if not node:
            return (-1, -1)
        left_diameter, left_height = self.getDiameterAndHeight(node.left)
        right_diamter, right_height = self.getDiameterAndHeight(node.right)
        diameter = max(left_diameter, right_diamter, 2 + left_height + right_height)
        return (diameter, 1 + max(left_height, right_height))

17. Validate Binary Search Tree

Intuition

The value of a node in a binary search tree has to be smaller or larger than the value of its parent based on the subtree it’s on and has to be larger or smaller than its child based on the child’s substree. The trick is realizing that for the leftmost node it has to be larger than minus infinity and for the rightmost node it has to be smaller than infinity. This means that the two infinities need adopting as the first limits.

Algorithm

Define a recursive function that basically performs depth-first search 1. Parameters are node to check, left constraint, and right constraint. 2. Base case: if node is None, return True. If node lies outside the constraint, return False. 3. Call the recursive helper function on the left child and the right child.

Complexity

Time complexity: \(O(n)\) - iterate through every node in the tree
Space complexity: \(O(n)\) - possible size of the recursion stack. This is essentially depth-first search. The average case is \(O(\log n)\)

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
# Instead of just comparing child to parent,
# see if the child is in an interval constrained
# by parent and another value
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def valid(node, left, right):
            if not node:
                return True
            if not (left < node.val < right):
                return False
            
            return (valid(node.left, left, node.val) and
                    valid(node.right, node.val, right))
        return valid(root, float('-inf'), float('inf'))

18. Lowest Common Ancestor of a Binary Tree

Intuition

At a node, there are three cases: 1. It is p and it is the ancestor of q. 2. It is q and it is the ancestor of p. 3. It is the ancestor of both p and q, each belonging to a different subtree.

Recursion is your friend here. The return value would be the node itself if it is None, p, or q. Calling the recursive function on its children in a bottom-up manner, if it is case 3, both left and right subtrees will return a non-null node, otherwise one of the subtree will return None.

Algorithm

Base case: return root itself if it is None, p, or q.
Recursion: call the method on the left and right children.
If both left and right results are non-null, return root. Else, return the non-null one. (The two nodes are guaranteed to be in the tree).

Complexity

Time complexity: \(O(n)\) - iterate through every node in the tree.
Space complexity: \(O(n)\) - average \(O(\log n)\) - the height of the recursion call stack.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None or root == p or root == q:
            return root
        
        left_ancestor = self.lowestCommonAncestor(root.left, p, q)
        right_ancestor = self.lowestCommonAncestor(root.right, p, q)

        if left_ancestor and right_ancestor:
            return root
        
        return left_ancestor or right_ancestor

19. Binary Tree Right Side View

Intuition

This is essentially breadth-first traversal, with a twist: 1. Travel each level from right to left. 2. Only record the first value encountered.

Algorithm

Base case: return None for root is None.
Breadth-first traversal: initialize a queue with the root and a result list.
While the queue is not empty:
1. For the current level in the queue, popleft each element.
2. If it is part of the right side view, append it to the result list. Else, do nothing
3. Add the children, prioritize the right child.
Return the result list.

Complexity

Time complexity: \(O(n)\) - iterate through every node in the tree.
Space complexity: \(O(n)\) - maximum size of the queue.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return
        
        right_side = deque([root])
        result = []
        
        while right_side:
            for i in range(len(right_side)):
                node = right_side.popleft()
                if i == 0:
                    result.append(node.val)
                if node.right:
                    right_side.append(node.right)
                if node.left:
                    right_side.append(node.left)
        return result

20. Kth Smallest Element in a BST

Intuition

The algorithm preorderly traverses the binary search tree, which is essentially flattening it out into a sorted array. However, I do not need to wait until the tree has been fully flattened but can iterate through the values as they are generated. Preorder traversal.

Algorithm

Perform preorder traversal on the BST. For each element generated, decrement k until it hits 0, when I need to return the value.

Complexity

Time complexity: \(O(n)\) - Iterate through every node in the tree.
Space complexity: \(O(\log n)\) to \(O(n)\) - The size of the recursion call stack.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []

        while True:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if not k:
                return root.val
            root = root.right

Tree

Definitions

Categories

Notes:

1. Breadth-first search

2. Depth-first search

3. Recursion

Problems

1. Flatten Binary Tree to Linked List

Intuition

Algorithm

Complexity

Code

2. Binary Tree Level Order Traversal

Intuition

Algorithm

Complexity

Code

3. Binary Tree Zigzag Level Order Traversal

Intuition

Algorithm

Complexity

Code

4. Populating Next Right Pointers in Each Node

Intuition

Algorithm

Complexity

Code

5. Vertical Order Traversal of a Binary Tree

Intuition

Algorithm

Complexity

Code

5. Maximum Depth of Binary Tree

Intuition

Algorithm

Complexity

Code

6. Symmetric Tree

Intuition

Algorithm

Complexity

Code

7. Path Sum

Intuition

Algorithm

Complexity

Code

8. Construct Binary Tree from Inorder and Postorder Traversal

Intuition

Algorithm

Complexity

Code

8. Construct Binary Tree from Inorder and Postorder Traversal

Intuition

Algorithm

Complexity

Code

9. Populating Next Right Pointers in Each Node II

Intuition

Algorithm

Complexity

Code

10. Lowest Common Ancestor of a Binary Search Tree

Intuition

Algorithm

Complexity

Code

11. Serialize and Deserialize Binary Tree

Intuition

Algorithm

Complexity

Code

12. Invert Binary Tree

Intuition

Code

13. Same Tree

Intuition

Code

14. Subtree of Another Tree