Tree Data Structure Practice Question

by

Check Same binary Tree

Leet 100. Same Tree

When we first read the “Same Tree” problem, we often think of comparing the traversal results — like inorder, preorder, or postorder — of both trees. That’s a natural and valid idea, but it’s not necessary or ideal in this case.

Case 1 : Using one of the traverse like in-order, pre-order or post-order

  • Calculate inorder for both tree and compare both

Two different trees can have the same inorder,pre-order or post-order traversal.

Tree 1:       1
             / \
            2   3

Inorder: [2,1,3]          


Tree 2:       3
             /
            1
           /
          2
          
Inorder: [2,1,3]
Python

Just comparing both inorder, fails

Atleast two of inorder + pre-order or inorder + post-order is required, refer

Case 2 : Simultaneous Traversal

Vartiation 1 In-order (Left → Root → Right)

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

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False

        # Traverse left subtree first (inorder)
        if not self.isSameTree(p.left, q.left):
            return False

        # Then check current node
        if p.val != q.val:
            return False

        # Then traverse right subtree
        return self.isSameTree(p.right, q.right)
Python

Vartiation 2 : Pre-order (Root → Left → Right)

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

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True  # Both trees are empty
        if not p or not q:
            return False  # One is empty, the other is not
        if p.val != q.val:
            return False  # Values differ

        # Recursively check left and right subtrees
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
Python

Check Symmetric in binary Tree

LeetCode 101 Symmetric Tree

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: TreeNode) -> bool:
        def isMirror(p: TreeNode, q: TreeNode) -> bool:
            if not p and not q:
                return True
            if not p or not q:
                return False
            if p.val != q.val:
                return False
            return isMirror(p.left, q.right) and isMirror(p.right, q.left)

        return isMirror(root.left, root.right) if root else True
Python

twist : Simultaneous Traversal but one is in left node, other in right node

Maximum Depth of Binary Tree

Leetcode 104. Maximum Depth of Binary Tree

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

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
Python

Tree Traversal Problems

Refer

LCA

What is the Lowest Common Ancestor (LCA)?

Given a binary tree (or general tree) and two nodes p and q, the Lowest Common Ancestor is the lowest node in the tree that has both p and q as descendants (a node can be a descendant of itself).

      3
     / \
    5   1
   / \ / \
  6  2 0  8
    / \
   7   4


LCA(5, 1) = 3

LCA(5, 4) = 5 (since a node can be ancestor of itself)

LCA(7,2) = 2 (furthest from the root in depth, not 3, its nearest)
Python

Key Observations

  • “Lowest” means furthest from the root in depth.
  • LCA is unique for any two nodes in a connected tree. i.e there only one unique path between nodes.
  • LCA exists only if both nodes are in the tree.

It’s a common subproblem in:

  • Tree queries
  • Network routing
  • Version control (common commit)
  • XML/DOM hierarchy navigation

Simple Recursive DFS (Binary Tree)

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    if left and right:
        return root
    return left or right
Python

  • Time: O(N)
  • Space: O(H) recursion stack

There are many other way as well to solve this

  • Path-to-Root Method
  • Binary Lifting
  • Tarjan’s Offline LCA (Union-Find)

Where LCA Useful?

  • Organizational chart
CEO
 ├── Manager1
 │    ├── EmployeeA
 │    └── EmployeeB
 └── Manager2
      └── EmployeeC

LCA(EmployeeA, EmployeeB) = Manager1

LCA(EmployeeA, EmployeeC) = CEO

Used in HR systems to find common supervisor.
Python

  • File System Paths
/
├── home
│    ├── user
│    │    ├── docs
│    │    └── pics
└── var


LCA(/home/user/docs/file1, /home/user/pics/file2) = /home/user

Used in file diff tools or finding shared base directory.
Python

  • Network Routing: If two devices are in a network tree, the LCA is the router/switch where their paths first meet. Helps in finding shortest routes.
  • Git Version Control: Every commit forms a tree (DAG). LCA of two commits is the merge base commit.

Competitive Programming Usage

  • Distance between two nodes
    • distance(a, b) = depth[a] + depth[b] – 2 * depth[LCA(a, b)]
  • Finding relationships (e.g., family tree — “closest common ancestor”)
  • Subtree queries: Knowing LCA helps restrict range of search.
  • Is X in the path between Y and Z?
  • Find the number of turns in path between two nodes
  • Count distinct values in path between nodes

LCA is often precomputed to answer queries in O(1) or O(log N).

Complete LCA 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

def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    if not root or root == p or root == q:
        return root

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

    if left and right:
        return root
    return left or right

# ------------------------------
# Build the example tree:
#         3
#        / \
#       5   1
#      / \ / \
#     6  2 0  8
#       / \
#      7   4

root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)

# Example nodes
p = root.left          # Node with value 5
q = root.left.right.right  # Node with value 4

# Find LCA
lca = lowestCommonAncestor(root, p, q)
print(f"LCA of {p.val} and {q.val} is: {lca.val}")
Python

Distance Between Two Nodes

Find distance between nodes p and q:

distance(p,q)=depth(p)+depth(q)−2×depth(lca)
Python

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

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    if left and right:
        return root
    return left or right

def findDepth(root, target, depth=0):
    if not root:
        return -1
    if root == target:
        return depth
    left = findDepth(root.left, target, depth + 1)
    if left != -1:
        return left
    return findDepth(root.right, target, depth + 1)

def distanceBetweenNodes(root, p, q):
    lca = lowestCommonAncestor(root, p, q)
    d1 = findDepth(lca, p)
    d2 = findDepth(lca, q)
    return d1 + d2

# Example tree:
#         1
#        / \
#       2   3
#      / \   \
#     4   5   6
#        / \
#       7   8

# Create nodes
n1 = TreeNode(1)
n2 = TreeNode(2)
n3 = TreeNode(3)
n4 = TreeNode(4)
n5 = TreeNode(5)
n6 = TreeNode(6)
n7 = TreeNode(7)
n8 = TreeNode(8)

# Build tree
n1.left, n1.right = n2, n3
n2.left, n2.right = n4, n5
n3.right = n6
n5.left, n5.right = n7, n8

# Example usage
print(distanceBetweenNodes(n1, n7, n6))  # Output: 5
print(distanceBetweenNodes(n1, n4, n8))  # Output: 4
Python

Check If a Node Lies on the Path

Check node x exist in path from nodes u to v

x lies on the path u → v if and only if:

dist(u,v)=dist(u,x)+dist(x,v)
Python

Because if x is between them, then going from u to v is the same as u → x + x → v.

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

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    if left and right:
        return root
    return left or right

def findDepth(root, target, depth=0):
    if not root:
        return -1
    if root == target:
        return depth
    left = findDepth(root.left, target, depth + 1)
    if left != -1:
        return left
    return findDepth(root.right, target, depth + 1)

def distanceBetweenNodes(root, p, q):
    lca = lowestCommonAncestor(root, p, q)
    d1 = findDepth(lca, p)
    d2 = findDepth(lca, q)
    return d1 + d2

def isNodeOnPath(root, u, v, x):
    dist_uv = distanceBetweenNodes(root, u, v)
    dist_ux = distanceBetweenNodes(root, u, x)
    dist_xv = distanceBetweenNodes(root, x, v)
    return dist_uv == dist_ux + dist_xv

# Example tree:
#         1
#        / \
#       2   3
#      / \   \
#     4   5   6
#        / \
#       7   8

# Build tree nodes
n1 = TreeNode(1)
n2 = TreeNode(2)
n3 = TreeNode(3)
n4 = TreeNode(4)
n5 = TreeNode(5)
n6 = TreeNode(6)
n7 = TreeNode(7)
n8 = TreeNode(8)

# Build tree structure
n1.left, n1.right = n2, n3
n2.left, n2.right = n4, n5
n3.right = n6
n5.left, n5.right = n7, n8

# Test
print(isNodeOnPath(n1, n7, n6, n1))  # True (1 is on path 7→6)
print(isNodeOnPath(n1, n7, n6, n2))  # True (2 is on path 7→6)
print(isNodeOnPath(n1, n4, n8, n3))  # False (3 not on path 4→8)
Python

Practice

Leetcode 222 Count Complete Tree Nodes

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1+ self.countNodes(root.left)+self.countNodes(root.right)
Python

LeetCode 102 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
    Python

    Leetcode 103 Binary Tree Zigzag Level Order Traversal

    from collections import deque

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:

        if not root:
            return []

        dp = deque([root])
        result = []
        flag = False

        while dp:
            temp = []

            for _ in range(len(dp)):
                node = dp.popleft()

                if flag:
                    temp.insert(0,node.val)
                else:
                    temp.append(node.val)

                if node.left:
                    dp.append(node.left)

                if node.right:
                    dp.append(node.right)

            result.append(temp)

            flag= False if flag else True

        return result
    Python

    It’s a special case of 102

    Further read

    • binary lifting
    • Tree Dynamic Programming (Tree DP)
      • Max sum of non-adjacent nodes
      • Subtree sum
      • Longest path in tree (diameter via DP)
      • DP with rerooting

    Leave a Comment