Trees and Binary Search Trees

Introduction

Tree data structures are fundamental in computer science, representing hierarchical relationships between data. Binary trees and Binary Search Trees (BST) are among the most important tree structures, forming the foundation for many algorithms and data structures.

In this article, we’ll explore tree concepts through practical LeetCode problems, providing clean, well-explained solutions in both C# and Python.

What is a Tree?

A tree is a hierarchical data structure consisting of:

• Nodes: The elements of the tree
• Root: The topmost node
• Parent/Child relationships: Each node (except root) has exactly one parent
• Leaves: Nodes with no children

Key Tree Properties:

• Height: The longest path from root to any leaf
• Depth: The distance from root to a specific node
• Level: All nodes at the same depth
• Subtree: A tree formed by a node and all its descendants

Binary Trees

A binary tree is a tree where each node has at most two children:

• Left child: The left subtree
• Right child: The right subtree

Tree Traversal Methods:

Preorder (Root → Left → Right): Visit root, then left subtree, then right subtree Inorder (Left → Root → Right): Visit left subtree, then root, then right subtree Postorder (Left → Right → Root): Visit left subtree, then right subtree, then root Level Order: Visit nodes level by level from top to bottom

Binary Search Trees (BST)

A Binary Search Tree is a binary tree with the following property:

• All nodes in the left subtree have values less than the root
• All nodes in the right subtree have values greater than the root
• Both left and right subtrees are also BSTs

This property enables efficient search, insertion, and deletion operations with O(log n) average time complexity.

Problem 1: Minimum Depth of Binary Tree

Problem Statement

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Understanding the Problem

We need to find the shortest path from root to any leaf. Unlike maximum depth, we must be careful: if a node has only one child, we cannot use the null child in our calculation.

Solution Strategy

Use DFS with recursion:

1. Base case: If root is null, return 0
2. If a node has only one child, we must follow that child (cannot use null)
3. If a node has both children, take the minimum of both subtrees
4. Add 1 for the current node

C# Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution 
{
    public int MinDepth(TreeNode root) 
    {
        // Base case: empty tree
        if (root == null) 
            return 0;
        
        // If left subtree is empty, must go right
        if (root.left == null) 
            return MinDepth(root.right) + 1;
        
        // If right subtree is empty, must go left
        if (root.right == null) 
            return MinDepth(root.left) + 1;
        
        // Both children exist: take minimum of both subtrees
        return 1 + Math.Min(MinDepth(root.right), MinDepth(root.left));
    }
}

Python 3 Solution

# 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
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        
        if root.right is None:
            return 1 + self.minDepth(root.left)
        
        if root.left is None:
            return 1 + self.minDepth(root.right)
        
        return 1 + min(self.minDepth(root.right), self.minDepth(root.left))

Complexity Analysis

• Time Complexity: O(n) where n is the number of nodes
• Space Complexity: O(h) where h is the height of the tree (recursion stack)

Problem 2: Merge Two Binary Trees

Problem Statement

You are given two binary trees root1 and root2. Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the non-null node will be used as the node of the new tree.

Understanding the Problem

We need to combine two trees by:

• Summing values when both nodes exist
• Using the existing node when only one exists
• Returning null when both are null

Solution Strategy

Use recursive DFS:

1. If both nodes are null, return null
2. If one is null, return the other
3. If both exist, create a new node with summed values
4. Recursively merge left and right subtrees

C# Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution 
{
    public TreeNode MergeTrees(TreeNode root1, TreeNode root2) 
    {
        // Both are null: return null
        if (root1 == null && root2 == null) 
            return null;
        
        // One is null: return the other
        if (root1 == null) 
            return root2;
        
        if (root2 == null) 
            return root1;
        
        // Both exist: create new node with summed values
        TreeNode root = new TreeNode(root1.val + root2.val);
        
        // Recursively merge left and right subtrees
        root.left = MergeTrees(root1.left, root2.left);
        root.right = MergeTrees(root1.right, root2.right);
        
        return root;
    }
}

Python 3 Solution

# 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
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 is None and root2 is None:
            return None
        
        if root1 is None:
            return root2
        
        if root2 is None:
            return root1
        
        root = TreeNode(root1.val + root2.val)
        root.left = self.mergeTrees(root1.left, root2.left)
        root.right = self.mergeTrees(root1.right, root2.right)
        
        return root

Complexity Analysis

• Time Complexity: O(min(m, n)) where m and n are the number of nodes in each tree
• Space Complexity: O(min(m, n)) for the recursion stack

Problem 3: Convert Sorted Array to Binary Search Tree

Problem Statement

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Understanding the Problem

To create a height-balanced BST from a sorted array:

• The middle element should be the root
• Left half forms the left subtree
• Right half forms the right subtree
• This ensures balance and maintains BST property

Solution Strategy

Divide and Conquer with Recursion:

1. Select the middle element as root
2. Recursively build left subtree from left subarray
3. Recursively build right subtree from right subarray
4. Return the root

C# Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution 
{
    public TreeNode SortedArrayToBST(int[] nums) 
    {
        if (nums.Length == 0)
            return null;
        
        // The middle of the array is the root node
        int middle = nums.Length / 2;
        
        // Create root node
        TreeNode root = new TreeNode(nums[middle]);
        
        // Recursively build left and right subtrees
        root.left = SortedArrayToBST(nums[..middle]);
        root.right = SortedArrayToBST(nums[(middle + 1)..]);
        
        return root;
    }
}

Python 3 Solution

# 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
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        
        middle = len(nums) // 2
        root = TreeNode(nums[middle])
        root.left = self.sortedArrayToBST(nums[:middle])
        root.right = self.sortedArrayToBST(nums[middle + 1:])
        
        return root

Complexity Analysis

• Time Complexity: O(n) where n is the number of elements
• Space Complexity: O(log n) for the recursion stack (height of balanced tree)

Problem 4: Path Sum

Problem Statement

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Understanding the Problem

We need to check if there exists any path from root to a leaf where the sum of node values equals targetSum. We traverse the tree, subtracting each node’s value from targetSum until we reach a leaf.

Solution Strategy

Use DFS recursion:

1. Base case: If root is null, return false
2. If we reach a leaf and remaining sum equals the leaf value, return true
3. Subtract current node value from targetSum
4. Recursively check left and right subtrees

C# Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution 
{
    public bool HasPathSum(TreeNode root, int targetSum) 
    {
        if (root == null) 
            return false;
        
        // If we reach a leaf and root.val equals remaining targetSum, path found
        if (root.left == null && root.right == null && root.val == targetSum) 
            return true;
        
        // Decrement targetSum by current node value
        targetSum -= root.val;
        
        // Check if path exists in left or right subtree
        return HasPathSum(root.left, targetSum) || HasPathSum(root.right, targetSum);
    }
}

Python 3 Solution

# 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
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root is None:
            return False
        
        if (root.right is None and root.left is None and root.val == targetSum):
            return True
        
        targetSum -= root.val
        return self.hasPathSum(root.right, targetSum) or self.hasPathSum(root.left, targetSum)

Complexity Analysis

• Time Complexity: O(n) where n is the number of nodes
• Space Complexity: O(h) where h is the height of the tree

Problem 5: Binary Tree Level Order Traversal

Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Understanding the Problem

Level order traversal visits nodes level by level from top to bottom. This is a BFS problem where we process all nodes at the current level before moving to the next level.

Solution Strategy

Use BFS with a Queue:

1. Enqueue the root
2. While queue is not empty:
   • Process all nodes at current level (queue size)
   • Add their values to current level list
   • Enqueue children for next level
3. Add current level to result

C# Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution 
{
    public IList<IList<int>> LevelOrder(TreeNode root) 
    {
        var result = new List<IList<int>>();
        Queue<TreeNode> queue = new Queue<TreeNode>();
        
        if (root == null) 
            return result;
        
        queue.Enqueue(root);
        
        while (queue.Count > 0)
        {
            int size = queue.Count; // Number of nodes at current level
            var currentLevel = new List<int>();
            
            // Process all nodes at current level
            for (int i = 0; i < size; i++)
            {
                TreeNode node = queue.Dequeue();
                currentLevel.Add(node.val);
                
                // Enqueue children for next level
                if (node.left != null) 
                    queue.Enqueue(node.left);
                
                if (node.right != null) 
                    queue.Enqueue(node.right);
            }
            
            result.Add(currentLevel);
        }
        
        return result;
    }
}

Python 3 Solution

# 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
import collections

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []
        queue = collections.deque([root])
        
        if root is None:
            return result
        
        while queue:
            size = len(queue)
            currentLevel = []
            
            for _ in range(size):
                node = queue.popleft()
                currentLevel.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                
                if node.right:
                    queue.append(node.right)
            
            result.append(currentLevel)
        
        return result

Complexity Analysis

• Time Complexity: O(n) where n is the number of nodes
• Space Complexity: O(n) for the queue (worst case: complete binary tree)

Problem 6: Binary Tree Zigzag Level Order Traversal

Problem Statement

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

Understanding the Problem

Similar to level order traversal, but we alternate the direction:

• Level 0: left to right
• Level 1: right to left
• Level 2: left to right
• And so on…

Solution Strategy

Use BFS with a Queue and a flag to track direction:

1. Use same BFS approach as level order
2. Use a zigzag flag to alternate direction
3. When zigzag is true, insert at beginning of list (reverse order)
4. When zigzag is false, append to end (normal order)
5. Toggle flag after each level

C# Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution 
{
    public IList<IList<int>> ZigzagLevelOrder(TreeNode root) 
    {
        IList<IList<int>> result = new List<IList<int>>();
        
        if (root == null) 
            return result;
        
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        bool zigzag = false; // Direction flag
        
        while (queue.Count > 0)
        {
            List<int> level = new List<int>();
            int size = queue.Count;
            
            for (int i = 0; i < size; i++)
            {
                TreeNode node = queue.Dequeue();
                
                // If zigzag is true, insert at beginning (reverse order)
                if (zigzag)
                {
                    level.Insert(0, node.val);
                }
                else
                {
                    level.Add(node.val);
                }
                
                // Enqueue children
                if (node.left != null)
                    queue.Enqueue(node.left);
                
                if (node.right != null)
                    queue.Enqueue(node.right);
            }
            
            result.Add(level);
            zigzag = !zigzag; // Toggle direction for next level
        }
        
        return result;
    }
}

Python 3 Solution

# 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
from queue import Queue

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []
        
        if root is None:
            return result
        
        queue = Queue()
        queue.put(root)
        zigzag = False
        
        while not queue.empty():
            level = []
            size = queue.qsize()
            
            for _ in range(size):
                node = queue.get()
                
                if zigzag:
                    level.insert(0, node.val)
                else:
                    level.append(node.val)
                
                if node.left:
                    queue.put(node.left)
                
                if node.right:
                    queue.put(node.right)
            
            result.append(level)
            zigzag = not zigzag
        
        return result

Complexity Analysis

• Time Complexity: O(n) where n is the number of nodes
• Space Complexity: O(n) for the queue

Problem 7: Validate Binary Search Tree

Problem Statement

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key
• The right subtree of a node contains only nodes with keys greater than the node’s key
• Both the left and right subtrees must also be binary search trees

Understanding the Problem

For a BST to be valid, an inorder traversal must produce values in strictly ascending order. We can use an iterative inorder traversal with a stack to check this property.

Solution Strategy

Iterative Inorder Traversal with Stack:

1. Use a stack to perform inorder traversal (Left → Root → Right)
2. Keep track of the previous node value
3. If current value is less than or equal to previous, it’s not a valid BST
4. Otherwise, continue traversal

C# Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution 
{
    public bool IsValidBST(TreeNode root) 
    {
        if (root == null) 
            return true;
        
        TreeNode previous = null;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        
        // Perform iterative inorder traversal
        while (root != null || stack.Count > 0)
        {
            // Go to leftmost node
            while (root != null)
            {
                stack.Push(root);
                root = root.left;
            }
            
            // Process current node
            root = stack.Pop();
            
            // Check BST property: current value must be greater than previous
            if (previous != null && root.val <= previous.val) 
                return false;
            
            previous = root;
            root = root.right; // Move to right subtree
        }
        
        return true;
    }
}

Python 3 Solution

# 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
from collections import deque

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        
        previous = None
        stack = deque()
        
        while root or len(stack) > 0:
            while root:
                stack.append(root)
                root = root.left
            
            root = stack.pop()
            
            if previous and root.val <= previous.val:
                return False
            
            previous = root
            root = root.right
        
        return True

Complexity Analysis

• Time Complexity: O(n) where n is the number of nodes
• Space Complexity: O(h) where h is the height of the tree

Problem 8: Construct Binary Tree from Preorder and Inorder Traversal

Problem Statement

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Understanding the Problem

Key Insight:

• Preorder: Root → Left → Right (first element is always the root)
• Inorder: Left → Root → Right (elements before root are left subtree, after root are right subtree)

Algorithm:

1. First element of preorder is the root
2. Find root in inorder array
3. Elements before root in inorder form left subtree
4. Elements after root in inorder form right subtree
5. Recursively build left and right subtrees

Solution Strategy

Recursive Divide and Conquer:

1. Base case: If arrays are empty, return null
2. Root is first element of preorder
3. Find root index in inorder
4. Split arrays: left subtree uses elements before root, right subtree uses elements after root
5. Recursively build subtrees

C# Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution 
{
    public TreeNode BuildTree(int[] preorder, int[] inorder) 
    {
        // Base case: empty arrays
        if (preorder.Length == 0 || inorder.Length == 0)
            return null;
        
        // Base case: single node
        if (preorder.Length == 1)
            return new TreeNode(preorder[0]);
        
        // Root is first element of preorder
        TreeNode root = new TreeNode(preorder[0]);
        
        // Find root index in inorder
        int rootIndex = Array.IndexOf(inorder, preorder[0]);
        
        // Recursively build left and right subtrees
        // Left subtree: preorder[1..rootIndex+1], inorder[..rootIndex]
        root.left = BuildTree(
            preorder[1..(rootIndex + 1)], 
            inorder[..rootIndex]
        );
        
        // Right subtree: preorder[rootIndex+1..], inorder[rootIndex+1..]
        root.right = BuildTree(
            preorder[(rootIndex + 1)..], 
            inorder[(rootIndex + 1)..]
        );
        
        return root;
    }
}

Python 3 Solution

# 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
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not inorder:
            return None
        
        if len(preorder) == 1:
            return TreeNode(preorder[0])
        
        root = TreeNode(preorder[0])
        rootIndex = inorder.index(preorder[0])
        
        root.left = self.buildTree(
            preorder[1:rootIndex + 1], 
            inorder[:rootIndex]
        )
        
        root.right = self.buildTree(
            preorder[rootIndex + 1:], 
            inorder[rootIndex + 1:]
        )
        
        return root

Complexity Analysis

• Time Complexity: O(n²) in worst case (due to index() operation), O(n log n) average
• Space Complexity: O(n) for the recursion stack

Key Takeaways

Tree Traversal Methods:

Preorder (Root → Left → Right): Useful for copying trees, prefix expressions Inorder (Left → Root → Right): Produces sorted order for BSTs Postorder (Left → Right → Root): Useful for deleting trees, postfix expressions Level Order (BFS): Processes nodes level by level, uses queue

When to Use DFS vs BFS:

DFS (Recursion/Stack):

• Finding paths
• Tree construction
• Tree validation
• Memory efficient for deep trees

BFS (Queue):

• Level order traversal
• Finding shortest paths
• Processing by levels
• Better for wide trees

Binary Search Tree Properties:

• Left subtree values < Root < Right subtree values
• Inorder traversal produces sorted sequence
• Enables efficient search, insert, delete operations
• Height-balanced BSTs maintain O(log n) operations

General Tree Problem Solving Tips:

1. Identify traversal pattern: Preorder, Inorder, Postorder, or Level Order?
2. Choose recursion or iteration: Recursion is cleaner, iteration uses less stack space
3. Handle null cases: Always check for null nodes
4. Track state: Use parameters to pass information down the tree
5. Base cases: Define clear termination conditions

Conclusion

Trees and Binary Search Trees are essential data structures in computer science. Understanding tree traversals, BST properties, and when to use DFS vs BFS will help you solve a wide variety of tree-related problems.

Key patterns to remember:

• DFS = “Go deep, process, backtrack”
• BFS = “Process level by level”
• BST = “Left < Root < Right”
• Inorder traversal = Sorted sequence for BSTs

Practice these algorithms with different problems to build strong intuition for tree manipulation and traversal.

Happy coding!