Binary Tree

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

Breadth-First Traversal (BFS)

from collections import deque

def bfs(root):
    if not root: return []

    result = []
    # If deque is not allowed, use lists to store current and next level
    queue = deque([root])

    while queue:
        curr = queue.popleft()
        result.append(curr.val)

        if curr.left:
            queue.append(curr.left)
        if curr.right:
            queue.append(curr.right)

    return result

Preorder traversal

• Used to create a copy of the tree

def preorderRecursive(root):
    if not root: return

    print(root.val)
    preorderRecursive(root.left)
    preorderRecursive(root.right)

def preorderIterative(root):
    stack = [root]

    while stack:
        node = stack.pop()
        print(node.val)
        # Push node.right first because stack is LIFO
        if node.right: stack.append(node.right)
        if node.left: stack.append(node.left)

Inorder traversal

• Used to get sorted values in a binary search tree

def inorderRecursive(root):
    if not root: return

    preorderRecursive(root.left)
    print(root.val)
    preorderRecursive(root.right)

def inorderIterative(root):
    curr, stack = root, []

    while curr or stack:
        # Always try to get leftmost child node
        while curr:
            stack.append(curr)
            curr = curr.left

        curr = stack.pop()
        print(curr.val)

        curr = curr.right

Postorder traversal

• Used to delete a tree starting from leaves to root

def postorderRecursive(root):
    if not root: return

    preorderRecursive(root.left)
    preorderRecursive(root.right)
    print(root.val)

def postorderIterative(root):
    stack, result = [root], []

    # Preorder is root -> left -> right
    # Modify preorder to root -> right -> left,
    #   then reverse result: left -> right -> root (== postorder)
    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push node.left first, opposite of preorder solution
        if node.left: stack.append(node.left)
        if node.right: stack.append(node.right)

    result.reverse()
    for node in result:
        print(node.val)

def maxDepth(root: Optional[TreeNode]) -> int:
    if not root:
        return 0

    left = self.maxDepth(root.left) + 1
    right = self.maxDepth(root.right) + 1
    return max(left, right)

Time: O(n)

Space: O(h), h = tree height

def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    if not p and not q:
        return True

    if (not p or not q) or p.val != q.val:
        return False

    left = self.isSameTree(p.left, q.left)
    right = self.isSameTree(p.right, q.right)
    return left and right

Time: O(n)

Space: O(h), h = tree height

Recursive:

def invertTree(root: Node) -> Node:
    if not root:
        return root

    left = self.invertTree(root.left)
    right = self.invertTree(root.right)
    root.left, root.right = root.right, root.left
    return root

Time: O(n)

Space: O(h), h = tree height

Iterative:

from collections import deque

def invertTree(root: Node) -> Node:
    if not root: return root

    q = deque()
    q.append(root)

    while q:
        node = q.popleft()
        node.left, node.right = node.right, node.left
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    return root

Time: O(n)

Space: O(n)

Recursive:

def isSymmetric(root: Node) -> bool:
    def helper(left, right) -> bool:
        if not left and not right: return True
        if not left or not right: return False
        if left.val != right.val: return False

        outer = helper(left.left, right.right)
        inner = helper(left.right, right.left)
        return outer and inner

    if not root: return False
    return helper(root.left, root.right)

Time: O(n)

Space: O(h), h = tree height

Iterative:

from collections import deque

# Time complexity: O(n)
# Space complexity: O(n)
def isSymmetric(root:Node) -> bool:
    if not root: return False

    q = deque()
    q.append(root.left)
    q.append(root.right)

    while q:
        left = q.popleft()
        right = q.popleft()
        if not left and not right: continue
        if not left or not right: return False
        if left.val != right.val: return False
        q.append(left.left)
        q.append(right.right)
        q.append(left.right)
        q.append(right.left)
    return True

def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    def helper(node, target, total):
        if not node:
            return False

        if not node.left and not node.right:
            return target == total + node.val

        left = helper(node.left, target, total + node.val)
        right = helper(node.right, target, total + node.val)
        return left or right

    return helper(root, targetSum, 0)

Time: O(n)

Space: O(h), h = tree height

# Time complexity: O((log n)^2)
# Space complexity: O(h), h = height of tree
def countNodes(root: Optional[TreeNode]) -> int:
    # getHeight() is O(log n) assuming complete binary tree
    # In a complete binary tree, n = h^2
    def getHeight(root):
        if not root: return 0
        return getHeight(root.left) + 1

    if not root: return 0

    left = getHeight(root.left)
    right = getHeight(root.right)

    # If equal subtree heights, left subtree is perfect binary tree
    if left == right:
        return countNodes(root.right) + 2**left
    # Else right subtree is perfect binary tree with one less height
    else:
        return countNodes(root.left) + 2**right

Time: O(log²n) assuming complete binary tree

Space: O(h), h = tree height

# In a preorder list, a node's left child is always the next element in the list
# In an inorder list, left side elements are left subtree of current node. Same with right
def buildTree(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    # Map inorder indices for O(1) lookup
    m = {}
    for i in range(len(inorder)):
        m[inorder[i]] = i

    # Recursively build left and right child nodes while shrinking list
    def helper(preI, inLeft, inRight):
        if preI >= len(preorder) or inLeft > inRight:
            return None

        inI = m[preorder[preI]]
        node = TreeNode(preorder[preI])

        node.left = helper(preI + 1, inLeft, inI - 1)
        # To get the current node's right child's index in preorder,
        # Skip the length of the entire left subtree
        # Left subtree length = inI - inLeft + 1
        node.right = helper(preI + inI - inLeft + 1, inI + 1, inRight)
        return node

    return helper(0, 0, len(inorder) - 1)

Time: O(n)

Space: O(n)

The solution is similar to "Construct Binary Tree from Preorder and Inorder Traversal". Notice that the output of postorder traversal is similar to preorder traversal, except postorder starts with right subtrees and the output is reversed.

def buildTree(inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    m = {}
    for i in range(len(inorder)):
        m[inorder[i]] = i

    def helper(postI, inLeft, inRight):
        if postI < 0 or inLeft > inRight:
            return None

        inI = m[postorder[postI]]
        node = TreeNode(postorder[postI])

        # To get the current node's left child's index in postorder,
        # Skip the length of the entire right subtree
        # Right subtree length = inRight - inI + 1
        node.left = helper(postI - (inRight - inI + 1), inLeft, inI - 1)
        node.right = helper(postI - 1, inI + 1, inRight)
        return node

    return helper(len(postorder) - 1, 0, len(inorder) - 1)

Time: O(n)

Space: O(n)

def connect(root: 'Node') -> 'Node':
    if not root: return root

    # Iterative breadth first traversal
    currLevel = [root]

    while currLevel:
        nextLevel = []
        for node in currLevel:
            if node.left: nextLevel.append(node.left)
            if node.right: nextLevel.append(node.right)

        for i in range(len(nextLevel) - 1):
            nextLevel[i].next = nextLevel[i + 1]

        currLevel = nextLevel

    return root

Time: O(n)

Space: O(n)

Follow-up: Use only constant space. Recursion using implicit stack space is fine.

def connect(root: 'Node') -> 'Node':
    # Treat each level as a linked list
    curr = root
    dummy = tail = Node()

    while curr:
        # Build pointers for next level
        if curr.left:
            tail.next = curr.left
            tail = tail.next
        if curr.right:
            tail.next = curr.right
            tail = tail.next
        curr = curr.next

        # Reached end of current level. Set pointers for next level
        # dummy.next is first node of next level
        if not curr:
            curr = dummy.next
            tail = dummy
            dummy.next = None

    return root

Time: O(n)

Space: O(1)

def flatten(root: Optional[TreeNode]) -> None:
    if not root: return

    # Make preorder list of nodes, then update node pointers
    nodes = []

    def helper(root):
        if not root: return

        nodes.append(root)
        helper(root.left)
        helper(root.right)

    helper(root)
    for i in range(len(nodes) - 1):
        nodes[i].left = None
        nodes[i].right = nodes[i + 1]

Time: O(n)

Space: O(n)

Follow-up: Use O(1) space.

def flatten(root: Optional[TreeNode]) -> None:
    # Remove the right subtree and attach to the rightmost node
    # in the left subtree. This preserves preorder
    curr = root

    while curr:
        if curr.left:
            # Find rightmost node in left subtree
            rightMostNode = curr.left
            while rightMostNode.right:
                rightMostNode = rightMostNode.right

            # Attach right subtree
            rightMostNode.right = curr.right

            # Move left subtree to right side
            curr.right = curr.left
            curr.left = None

        curr = curr.right

Time: O(n)

Space: O(1)

def sumNumbers(root: Optional[TreeNode]) -> int:
    paths = []

    def helper(node, pathVal):
        if not node: return

        pathVal = pathVal * 10 + node.val

        if not node.left and not node.right:
            paths.append(pathVal)
            return

        helper(node.left, pathVal)
        helper(node.right, pathVal)

    helper(root, 0)
    return sum(paths)

Time: O(n)

Space: O(h), h = tree height

class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        self.node = root

    # Iterative inorder traversal
    def next(self) -> int:
        # Get leftmost node
        # This loop runs at most n times.
        # If next() is called n times, average time complexity is O(1)
        while self.node:
            self.stack.append(self.node)
            self.node = self.node.left
        nextNode = self.stack.pop()

        # If nextNode.right is None, get next node from stack
        self.node = nextNode.right
        return nextNode.val

    def hasNext(self) -> bool:
        return bool(self.stack or self.node)

Time: O(1) average

Space: O(h), h = tree height

def lowestCommonAncestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if not root: return None

    # Return early if p/q found because LCA cannot be lower
    # If p/q is LCA, recursion will exit with p/q
    if root == p or root == q: return root

    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)

    # LCA is current node
    if left and right:
        return root

    # Answer will be carried up recursion stack
    return left or right

Time: O(n)

Space: O(h), h = tree height

def averageOfLevels(root: Optional[TreeNode]) -> List[float]:
    currLvl, answer = [root],  []

    while currLvl:
        nextLvl, total = [], 0
        for node in currLvl:
            total += node.val
            if node.left:
                nextLvl.append(node.left)
            if node.right:
                nextLvl.append(node.right)

        answer.append(total / len(currLvl))
        currLvl = nextLvl

    return answer

Time: O(n)

Space: O(n)

def rightSideView(root: Optional[TreeNode]) -> List[int]:
    if not root: return []

    # Iterative breadth first traversal
    currLvl, answer = [root], []

    while currLvl:
        answer.append(currLvl[-1].val)
        nextLvl = []
        for node in currLvl:
            if node.left:
                nextLvl.append(node.left)
            if node.right:
                nextLvl.append(node.right)
        currLvl = nextLvl

    return answer

Time: O(n)

Space: O(n)

Alternative answer:

def rightSideView(root: Optional[TreeNode]) -> List[int]:
    answer = []

    # Reversed preorder traversal
    def helper(root, depth: int) -> None:
        if not root: return

        if depth == len(answer):
            answer.append(root.val)

        helper(root.right, depth + 1)
        helper(root.left, depth + 1)

    helper(root, 0)
    return answer

Time: O(n)

Space: O(h), h = tree height

def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    if not root: return []

    currLvl, answer = [root], []

    while currLvl:
        answer.append([])
        nextLvl = []
        for node in currLvl:
            answer[-1].append(node.val)
            if node.left:
                nextLvl.append(node.left)
            if node.right:
                nextLvl.append(node.right)
        currLvl = nextLvl

    return answer

Time: O(n)

Space: O(n)

def zigzagLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    if not root: return []

    currLvl, answer, forward = [root], [], True

    while currLvl:
        vals = []
        for node in currLvl:
            vals.append(node.val)
        if not forward:
            vals.reverse()
        answer.append(vals)
        forward = not forward

        nextLvl = []
        for node in currLvl:
            if node.left:
                nextLvl.append(node.left)
            if node.right:
                nextLvl.append(node.right)
        currLvl = nextLvl

    return answer

Time: O(n)

Space: O(n)

def getMinimumDifference(root: Optional[TreeNode]) -> int:
    answer, prev = float("inf"), None

    # Inorder traversal, keep track of prev
    def helper(root):
        if not root: return

        helper(root.left)
        nonlocal answer, prev
        if prev:
            answer = min(answer, root.val - prev.val)
        prev = root
        helper(root.right)

    helper(root)
    return answer

Time: O(n)

Space: O(h), h = tree height

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    # Iterative inorder traversal
    curr, stack = root, []

    while stack or curr:
        while curr:
            stack.append(curr)
            curr = curr.left

        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        curr = node.right

    return -1

Time: O(n)

Space: O(h), h = tree height

Alternative solution:

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    count, answer = 0, 0

    # Recursive inorder traversal, counting nodes
    def helper(root):
        if not root: return

        helper(root.left)
        nonlocal count, answer
        count += 1
        if count == k:
            answer = root.val
            return
        helper(root.right)

    helper(root)
    return answer

Time: O(n)

Space: O(h), h = tree height

def isValidBST(root: Optional[TreeNode]) -> bool:
    stack, prev, curr = [], None, root

    # Iterative inorder traversal, tracking prev
    while stack or curr:
        while curr:
            stack.append(curr)
            curr = curr.left

        node = stack.pop()
        if prev and prev.val >= node.val:
            return False

        prev = node
        curr = node.right

    return True

Time: O(n)

Space: O(h), h = tree height

Alternative solution:

def isValidBST(root: Optional[TreeNode]) -> bool:
    # Recursive inorder traversal, updating valid value range
    def helper(root, minV, maxV):
        if not root: return True

        if root.val <= minV or root.val >= maxV:
            return False

        left = helper(root.left, minV, root.val)
        right = helper(root.right, root.val, maxV)
        return left and right

    return helper(root, float("-inf"), float("inf"))

Time: O(n)

Space: O(h), h = tree height