Tree

Question 1

Implement

BFS traversal of a tree
input: root of a tree
output: none; print the node instead as you visit in level order

Assume the following Tree Data Structure

class TreeNode:
    def \_\_init\_\_(self, val):
        self.val = val
        self.left = None
        self.right = None

Answer 1

from collections import deque

def bfs(root):
    if not root:
        return
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

Question 2

Implement

Morris Tree/Preorder Traversal To Flatten a Tree to a Linked List
Time Complexity: O(n)
Space Complexity: O(1)

class TreeNode:
    def \_\_init\_\_(self, val):
        self.val = val
        self.left = None
        self.right = None

Answer 2

def flatten(root):
    if not root:
         return root

    curr = root
    while curr:
        if curr.left:
            # Find predecessor (rightmost node in left subtree)
            pred = curr.left
            while pred.right:
                pred = pred.right

            # Connect predecessor to curr.right
            pred.right = curr.right
            # Move left subtree to the right
            curr.right = curr.left
            curr.left = None
        
        # Move to next right node
        curr = curr.right
   return root

Question 3

Solve

Given a postorder and inorder lists, reconstruct a binary tree. Assume the lists contains unique values

Answer 3

def buildTree(inorder, postorder):
    index_map = {val: idx for idx, val in enumerate(inorder)}
    post_idx = len(postorder) - 1

    def helper(in_left, in_right):
        nonlocal post_idx
        if in_left > in_right:
            return None

        root_val = postorder[post_idx]
        post_idx -= 1
        root = TreeNode(root_val)

        idx = index_map[root_val]

        root.right = helper(idx + 1, in_right)
        root.left = helper(in_left, idx - 1)

        return root

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