Skip to main content

Poridhi: Trees & BST


Trees & BST related problems:

This blog post presents essential Python solutions for foundational binary tree problems, frequently encountered in coding interviews and algorithm practice. It begins by solving how to determine the maximum depth of a binary tree, which measures the height of the tree using recursion. Next, it explains how to invert a binary tree, flipping the left and right children recursively. The level order traversal solution demonstrates how to use a queue for breadth-first search to return all nodes level by level. To check whether a tree is a mirror of itself (symmetric tree), it uses a recursive helper function comparing mirrored subtrees.

Further, the blog tackles validation of a binary search tree (BST) by checking whether each node falls within valid numeric boundaries during traversal. It then demonstrates how to find the lowest common ancestor (LCA) of two nodes in a BST using value comparisons. Lastly, the post includes a method to construct a binary tree from preorder and inorder traversal arrays, a classic problem that teaches recursive tree construction based on traversal rules. Each solution is written concisely in Python with clarity in logic and structure, making it ideal for learners and interview preparation.

✅ Maximum Depth of Binary Tree

def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

✅ Invert Binary Tree

def invertTree(root):
    if root:
        root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root

✅ Binary Tree Level Order Traversal

from collections import deque

def levelOrder(root):
    if not root:
        return []
    
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            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

✅ Symmetric Tree

def isSymmetric(root):
    def isMirror(t1, t2):
        if not t1 and not t2:
            return True
        if not t1 or not t2:
            return False
        return t1.val == t2.val and \
               isMirror(t1.left, t2.right) and \
               isMirror(t1.right, t2.left)
    
    return isMirror(root, root)

✅ Validate Binary Search Tree

def isValidBST(root):
    def validate(node, low=float('-inf'), high=float('inf')):
        if not node:
            return True
        if not (low < node.val < high):
            return False
        return validate(node.left, low, node.val) and \
               validate(node.right, node.val, high)
    
    return validate(root)

✅ Lowest Common Ancestor of a BST

def lowestCommonAncestor(root, p, q):
    if p.val < root.val and q.val < root.val:
        return lowestCommonAncestor(root.left, p, q)
    elif p.val > root.val and q.val > root.val:
        return lowestCommonAncestor(root.right, p, q)
    else:
        return root

✅ Construct Binary Tree from Preorder and Inorder Traversal

def buildTree(preorder, inorder):
    if not preorder or not inorder:
        return None
    
    root_val = preorder[0]
    root = TreeNode(root_val)
    mid = inorder.index(root_val)
    
    root.left = buildTree(preorder[1:mid+1], inorder[:mid])
    root.right = buildTree(preorder[mid+1:], inorder[mid+1:])
    
    return root

Comments

Post a Comment

Popular posts from this blog

Poridhi: Stacks & Queues

  Stacks & Queues related problems: This collection of solutions tackles three classic problems often encountered in technical interviews and competitive programming. The Valid Parentheses problem checks whether a string has properly matched and ordered brackets using a stack. The Sliding Window Maximum efficiently finds the maximum value in every window of size k across an array using a deque, a popular sliding window pattern that ensures optimal performance. The Stock Span Problem simulates a real-world stock analysis scenario and calculates the number of consecutive days before today for which the stock price was less than or equal to today's, also utilizing a stack for efficient computation. These problems test understanding of stacks, queues, and sliding window techniques. ✅ Valid Parentheses def isValid ( s: str ) -> bool : stack = [] mapping = { ')' : '(' , '}' : '{' , ']' : '[' } for char in s: ...
Post a Comment
Read more

Data Recovery: DevOps pre-state learning

  Data Backup Data backup is the practice of copying data from a primary to a secondary location, to protect it in case of equipment failure, cyberattack, natural disaster or other data loss events. This can include documents, media files, configuration files, machine images, operating systems, and registry files. Essentially, any data that we want to preserve can be stored as backup data. Data Restore Data restore is the process of copying backup data from secondary storage and restoring it to its original location or a new location. A restore is performed to return data that has been lost, stolen or damaged to its original condition or to move data to a new location. Pilot Light A pilot light approach minimizes the ongoing cost of disaster recovery by minimizing the active resources, and simplifies recovery at the time of a disaster because the core infrastructure requirements are all in place. Warm Standby The warm standby approach involves ensuring that there is a scaled down, ...
Post a Comment
Read more

Poridhi: Basic Programming & Math

Basic Programming and math related problems: Extracting digits means breaking a number like 1234 into [1, 2, 3, 4], often using string conversion or modulo/division. Counting digits involves finding how many digits are in a number using length of a string or repeated division. Reversing an integer flips its digits (e.g., 123 becomes 321), with care for signs and 32-bit limits. A palindrome number reads the same forward and backward, often checked by comparing the original and reversed number. Armstrong numbers are those equal to the sum of their digits each raised to the number of digits, like 153 = 1³ + 5³ + 3³. To find the sum of all divisors of a number, loop through integers and check which divide the number without a remainder. Prime numbers are only divisible by 1 and themselves, and checking up to the square root is efficient. GCD, the greatest common divisor of two numbers, can be found using a simple loop or more efficiently with the Euclidean algorithm, which uses repeated mo...
Post a Comment
Read more