Haijun Si

Leetcode week #5: Binary Trees

Jul 29, 2024 | monday 6:20 pm

This series main purpose is for my own accountability and reference, as well as anyone who wants to follow my journey to becoming a better problem solver. Each week, I will highlight problems that I thought was interesting or difficult. Additionally, other problems that I solved and their solutions are listed below.

  1. 🟑 Construct Binary Tree From Preorder And Inorder Traversal
  2. 🟒 Invert Binary Tree
  3. 🟒 Max Depth of Binary Tree
  4. 🟒 Diameter of Binary Tree
  5. 🟒 Balanced Binary Tree
  6. 🟒 Same Tree
  7. 🟒 Subtree of Another Tree
  8. 🟑 Lowest Common Ancestor of BST
  9. 🟑 Binary Tree Level Order Traversal
  10. 🟑 Binary Tree Right Side View
  11. 🟑 Count Good Nodes in Binary Tree
  12. 🟑 Validate Binary Search Tree
  13. 🟑 Kth Smallest Element in BST
  14. πŸ”΄ Binary Tree Max Path Sum
  15. πŸ”΄ Serialize and Deserialize Binary Tree

Construct Binary Tree From Preorder And Inorder Traversal

MediumBinary-tree

Try it yourself here!

This problem is particularly interesting as it requires a solid understanding of both preorder and inorder traversals to solve effectively. It also provides an excellent opportunity to compare and contrast Depth-First Search (DFS) and Breadth-First Search (BFS) approaches.

DFS vs BFS

BFS (Breadth-First Search): Explores all nodes at the present depth before moving on to nodes at the next depth level. DFS (Depth-First Search): Explores as far as possible along each branch before backtracking.

Problem Statement: The goal is to reconstruct a binary tree using two given lists: one representing the preorder traversal and another representing the inorder traversal of the tree.

Example:

preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output: [3,9,20,null,null,15,7].

The solution can be determined by analyzing both traversal lists:

By combining these properties, we can recursively construct the entire tree.

Solution:

DFS Algorithm:

  1. Base case: If the left pointer exceeds the right pointer, return None.
  2. Create a new node using the current preorder index value and increment the index.
  3. Find the index of this node’s value in the inorder traversal.
  4. Recursively construct the left subtree using the left portion of the inorder list.
  5. Recursively construct the right subtree using the right portion of the inorder list.
  6. Return the newly created node.

Complexity:

def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    def dfs(left, right):
        nonlocal preorder_index
        if left > right:
            return None
        node = preorder[preorder_index]
        preorder_index += 1
        newNode = TreeNode(node)
        newNode.left = dfs(left, indexMap[node] - 1)
        newNode.right = dfs(indexMap[node] + 1, right)
        return newNode
    
    indexMap = {}
    for i, v in enumerate(inorder):
        indexMap[v] = i
    preorder_index = 0
    
    return dfs(0, len(inorder) - 1)

Invert Binary Tree

EasyBinary-tree

Try it yourself here!

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root:
        return
    left_subtree = self.invertTree(root.left)
    right_subtree = self.invertTree(root.right)

    root.left = right_subtree
    root.right = left_subtree
    return root

Complexity:

Max Depth of Binary Tree

EasyBinary-tree

Try it yourself here!

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

Complexity:

Diameter of Binary Tree

EasyBinary-tree

Try it yourself here!

def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
    max_diameter = 0
    def getDiameter (root):
        nonlocal max_diameter
        if not root:
            return 0
        left_tree = getDiameter(root.left)
        right_tree = getDiameter(root.right)
        max_diameter = max(max_diameter, left_tree + right_tree)
        return 1 + max(left_tree, right_tree)
    getDiameter(root)
    return max_diameter

Complexity:

Balanced Binary Tree

EasyBinary-tree

Try it yourself here!

def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def balanced(node):
            if not node:
                return True, -1
            
            isLeftBalanced, leftHeight = balanced(node.left)
            if not isLeftBalanced:
                return False, 0
            isRightBalanced, rightHeight = balanced(node.right)
            if not isRightBalanced:
                return False, 0
            
            return (abs(rightHeight - leftHeight) < 2), 1 + max(leftHeight, rightHeight)
        
        return balanced(root)[0]

Complexity:

Same Tree

EasyBinary-tree

Try it yourself here!

def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        p_queue, q_queue = deque([p]), deque([q])
        while p_queue and q_queue:
            p_node = p_queue.popleft()
            q_node = q_queue.popleft()
            if not p_node and not q_node:
                continue
            if not p_node or not q_node or p_node.val != q_node.val:
                return False
            p_queue.append(p_node.left)
            p_queue.append(p_node.right)
            q_queue.append(q_node.left)
            q_queue.append(q_node.right)     
        return len(p_queue) == 0 and len(q_queue) == 0

Complexity:

Subtree of Another Tree

EasyBinary-tree

Try it yourself here!

def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def sameTree(p, q):
            if not p and not q:
                return True
            if not p or not q:
                return False
            return p.val == q.val and sameTree(p.left, q.left) and sameTree(p.right, q.right)
        
        q = deque([root])
        while q:
            node = q.popleft()
            if sameTree(node, subRoot):
                return True
            if node:
                q.append(node.left)
                q.append(node.right)
        return False

Complexity:

Lowest Common Ancestor of BST

MediumBinary-search-tree

Try it yourself here!

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        node = root
        while node:
            if p.val > node.val and q.val > node.val:
                node = node.right
            elif p.val < node.val and q.val < node.val:
                node = node.left
            else:
                return node

Complexity:

Binary Tree Level Order Traversal

MediumBinary-tree

Try it yourself here!

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

        q = deque([root])
        res = []
        while q:
            level_length = len(q)
            level = []
            for _ in range(level_length):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(level)
        return res

Complexity:

Binary Tree Right Side View

MediumBinary-tree

Try it yourself here!

def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        ans = []
        q = deque([root])
        while q:
            level_len = len(q)
            node = None
            for _ in range(level_len):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(node.val)
        return ans

Complexity:

Count Good Nodes in Binary Tree

MediumBinary-tree

Try it yourself here!

def goodNodes(self, root: TreeNode) -> int:
        if root is None:
            return 0
        count = 0
        def findGoodNodes(node, maxSoFar):
            nonlocal count
            if node.val >= maxSoFar:
                count += 1
            if node.left:
                findGoodNodes(node.left, max(node.val, maxSoFar))
            if node.right:
                findGoodNodes(node.right, max(node.val, maxSoFar))
        findGoodNodes(root, root.val)
        return count

Complexity:

Validate Binary Search Tree

MediumBinary-search-tree

Try it yourself here!

def isValidBST(self, root: Optional[TreeNode]) -> bool:
        ans = []
        def inOrder(node):
            if node is None:
                return
            inOrder(node.left)
            ans.append(node.val)
            inOrder(node.right)
        inOrder(root)
        for i in range(1, len(ans)):
            if ans[i] <= ans[i - 1]:
                return False
        return True

Complexity:

Kth Smallest Element in BST

MediumBinary-search-tree

Try it yourself here!

def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        ans = []
        def inOrder(node):
            if node is None:
                return
            inOrder(node.left)
            ans.append(node.val)
            inOrder(node.right)
        inOrder(root)
        return ans[k - 1]

Complexity:

Binary Tree Max Path Sum

HardBinary-tree

Try it yourself here!

def maxPathSum(self, root: Optional[TreeNode]) -> int:
        maxSum = float(-inf)
        def getSum(node):
            nonlocal maxSum
            if not node:
                return 0
            leftMax = max(getSum(node.left), 0)
            rightMax = max(getSum(node.right), 0)

            maxSum = max(maxSum, leftMax + rightMax + node.val)
            return max(leftMax, rightMax) + node.val
        
        getSum(root)
        return maxSum

Complexity:

Serialize and Deserialize Binary Tree

HardBinary-tree

Try it yourself here!

def serialize(self, root):
    if root == None: return ""
    q = deque([root])
    tree = []
    while q:
        node = q.popleft()
        if node:
            tree.append(str(node.val))
            q.extend([node.left, node.right])
        else:
            tree.append("*")
    return ','.join(tree)

def deserialize(self, data):
    if data == "": return None
    tree = deque(data.split(","))
    root = TreeNode(int(tree.popleft()))
    q = deque([root])
    while q:
        node = q.popleft()
        if (left := tree.popleft()) != "*":
            node.left = TreeNode(int(left))
            q.append(node.left)
        if (right := tree.popleft()) != "*":
            node.right = TreeNode(int(right))
            q.append(node.right)
    return root

Complexity: