Rahul Saxena

Rahul Saxena

he/him

CS Grad student at UMass Amherst

Binary Trees: A Comprehensive Guide

15 minute read

Published:

Binary trees are a fundamental data structure in computer science, often used in various applications ranging from databases to operating systems. Understanding the different types of problems and patterns associated with binary trees is essential for anyone looking to master data structures and algorithms. In this guide, we will explore key binary tree problem patterns and provide examples for each.

Prerequisites

Before diving into binary tree problems, it’s important to have a solid grasp of the following concepts:

  • Recursion
  • Stack and Queue data structures
  • Tree Traversals (Inorder, Preorder, Postorder)

Important Binary Tree Patterns

Pattern 1: Tree Traversals

Overview:

Tree traversals are fundamental operations in binary trees, where each node in the tree is visited in a systematic way. The most common traversals are Inorder, Preorder, and Postorder.

Problems:

Code Example (Inorder Traversal - Iterative):

// Iterative Inorder Traversal in C++
#include <vector>
#include <stack>

std::vector<int> inorderTraversal(TreeNode* root) {
    std::vector<int> result;
    std::stack<TreeNode*> stack;
    TreeNode* curr = root;
    
    while (curr != nullptr || !stack.empty()) {
        while (curr != nullptr) {
            stack.push(curr);
            curr = curr->left;
        }
        curr = stack.top();
        stack.pop();
        result.push_back(curr->val);
        curr = curr->right;
    }
    
    return result;
}

Pattern 2: Level Order Traversal

Overview: Level Order Traversal, also known as Breadth-First Search (BFS) for trees, involves visiting all the nodes level by level, from left to right. It’s commonly used to solve problems where you need to examine nodes on the same level of the tree.

Key Points:

  • Use a queue to keep track of nodes at the current level.
  • Process nodes level by level, adding their children to the queue.
  • This approach is particularly useful for problems that involve hierarchical data.

Problems:

Code Example (Level Order Traversal):

// Level Order Traversal in C++
#include <vector>
#include <queue>

std::vector<std::vector<int>> levelOrder(TreeNode* root) {
    std::vector<std::vector<int>> result;
    if (!root) return result;
    
    std::queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int size = q.size();
        std::vector<int> level;
        for (int i = 0; i < size; ++i) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(level);
    }
    
    return result;
}

Explanation:

• A queue is used to store nodes of the tree. • The size of the queue at each level is captured to determine the number of nodes on that level. • Nodes are processed one level at a time, and their children are added to the queue for the next level.

Pattern 3: Views of Binary Tree

Overview: The “views” of a binary tree refer to the nodes that are visible when the tree is viewed from different perspectives: top, left, right, and boundary views. These problems require traversing the tree in a way that simulates how the tree would look from a specific direction.

Key Points:

  • Top View: Nodes visible when the tree is viewed from the top.
  • Left View: Nodes visible when the tree is viewed from the left side.
  • Right View: Nodes visible when the tree is viewed from the right side.
  • Boundary View: Combination of the left boundary, leaves, and right boundary.

Problems:

Code Example (Right Side View):

// Right Side View of Binary Tree in C++
#include <vector>
#include <queue>

std::vector<int> rightSideView(TreeNode* root) {
    std::vector<int> result;
    if (!root) return result;
    
    std::queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            TreeNode* node = q.front();
            q.pop();
            if (i == size - 1) {
                result.push_back(node->val); // Last node on this level
            }
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    
    return result;
}

Explanation:

• A queue is used for level-order traversal. • For the right side view, the last node of each level is added to the result. • Similar approaches can be adapted for top, left, and boundary views, with modifications to focus on the specific nodes that should be visible.

Pattern 4: Binary Tree Properties and Depth Calculations

Overview: Binary tree properties and depth calculations involve determining various metrics related to the structure of a tree, such as its depth, height, diameter, and width. These problems often require recursive approaches to traverse the tree and calculate the desired properties.

Key Points:

  • Maximum/Minimum Depth: The number of nodes along the longest/shortest path from the root node down to the farthest/nearest leaf node.
  • Balanced Binary Tree: A binary tree is balanced if the depth of the two subtrees of every node never differs by more than one.
  • Diameter: The length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
  • Width: The maximum number of nodes at any level of the binary tree.

Problems:

Code Example (Maximum Depth of Binary Tree):

// Maximum Depth of Binary Tree in C++
#include <algorithm>

int maxDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return std::max(leftDepth, rightDepth) + 1;
}

Explanation:

• Maximum Depth: This is calculated by recursively finding the depth of the left and right subtrees and returning the maximum of the two, plus one for the current node. • Balanced Binary Tree: For checking if a tree is balanced, you can calculate the depth of each subtree and ensure that the difference is no more than one at every node. • Diameter: To find the diameter, calculate the depth of left and right subtrees for each node and track the maximum sum of these depths across all nodes. • Width: Use level order traversal to count the number of nodes at each level and keep track of the maximum.

Pattern 5: Lowest Common Ancestor (LCA)

Overview: The Lowest Common Ancestor (LCA) of two nodes in a binary tree is the deepest node that is an ancestor of both nodes. This concept is widely used in problems involving relationships between nodes in a tree, such as finding common ancestors or determining hierarchical structures.

Key Points:

  • LCA in Binary Tree: In a general binary tree, the LCA is found by recursively traversing the tree. If a node matches one of the target nodes, it’s returned as a potential LCA.
  • LCA in Binary Search Tree (BST): In a BST, the LCA can be found more efficiently by leveraging the properties of the BST. The search is guided by comparing node values.
  • Applications: LCA problems are often used in scenarios involving hierarchical data, such as organizational charts, genealogical trees, and file systems.

Problems:

Code Example (LCA in a Binary Tree):

// Lowest Common Ancestor in a Binary Tree in C++
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr || root == p || root == q) {
        return root;
    }

    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);

    if (left != nullptr && right != nullptr) {
        return root;
    }

    return left != nullptr ? left : right;
}

Explanation:

• Recursive Approach: The LCA is found by recursively searching the left and right subtrees. If both the left and right subtree contain one of the nodes, then the current node is the LCA. If only one subtree contains both nodes, that subtree contains the LCA. • Edge Cases: If either p or q is the root, then the root itself is the LCA. If both nodes are found in the same subtree, the LCA is in that subtree.

Applications:

• Genealogical Trees: Finding the common ancestor of two individuals in a family tree. • Organizational Hierarchies: Determining the nearest common manager of two employees. • File Systems: Finding the common directory of two files in a file system.

Pattern 6: Rooted Path - Root to Leaf

Overview: Rooted path problems involve finding and analyzing paths from the root node to leaf nodes in a binary tree. These problems often require calculating sums, checking for specific properties along the path, or generating all possible paths from the root to leaves.

Key Points:

  • Root to Leaf Paths: These problems generally require traversing the tree to collect or analyze the data from the root to each leaf node.
  • Path Sum Calculations: Many problems involve calculating the sum of node values along a root-to-leaf path and checking against a target sum.
  • Backtracking: Often, backtracking is used to explore all possible paths from the root to the leaf nodes, making sure to revert changes to the path as you backtrack up the tree.

Problems:

Code Example (Binary Tree Paths):

// Binary Tree Paths in C++
#include <vector>
#include <string>

void findPaths(TreeNode* node, std::string path, std::vector<std::string>& paths) {
    if (!node) return;
    
    path += std::to_string(node->val);
    
    if (!node->left && !node->right) {
        paths.push_back(path); // Leaf node
    } else {
        path += "->";
        findPaths(node->left, path, paths);
        findPaths(node->right, path, paths);
    }
}

std::vector<std::string> binaryTreePaths(TreeNode* root) {
    std::vector<std::string> paths;
    if (root) findPaths(root, "", paths);
    return paths;
}

Explanation:

• Recursive Traversal: The tree is traversed recursively, constructing a path string as you go from the root to each leaf node. • Leaf Nodes: When a leaf node is reached (a node with no children), the constructed path is added to the list of paths. • Backtracking: After exploring one path, the function backtracks to explore alternative paths from the root to other leaf nodes.

Applications:

• Path Generation: Generating all paths from the root to leaf nodes in hierarchical structures like file systems or organizational charts. • Sum Calculations: Problems that involve finding paths that sum up to a specific value, commonly used in financial or decision-making models.

Pattern 7: Tree Construction and Conversion

Overview: Tree construction and conversion problems involve creating a binary tree from given traversal orders or converting a tree into a different structure. These problems often require a deep understanding of tree properties and traversal methods.

Key Points:

  • Tree Construction from Traversals: These problems involve constructing a binary tree using given sequences of inorder, preorder, or postorder traversals.
  • Tree Conversion: These problems require transforming a binary tree into another structure, such as a linked list, string representation, or different binary tree form.
  • Recursive Approach: Tree construction typically involves recursive methods to correctly position nodes based on traversal orders.

Problems:

Code Example (Construct Binary Tree from Preorder and Inorder Traversal):

// Construct Binary Tree from Preorder and Inorder Traversal in C++
#include <unordered_map>

TreeNode* buildTreeHelper(const std::vector<int>& preorder, int preStart, int preEnd,
                          const std::vector<int>& inorder, int inStart, int inEnd,
                          std::unordered_map<int, int>& inorderMap) {
    if (preStart > preEnd || inStart > inEnd) {
        return nullptr;
    }

    int rootVal = preorder[preStart];
    TreeNode* root = new TreeNode(rootVal);
    int rootIndex = inorderMap[rootVal];
    int leftTreeSize = rootIndex - inStart;

    root->left = buildTreeHelper(preorder, preStart + 1, preStart + leftTreeSize,
                                 inorder, inStart, rootIndex - 1, inorderMap);
    root->right = buildTreeHelper(preorder, preStart + leftTreeSize + 1, preEnd,
                                  inorder, rootIndex + 1, inEnd, inorderMap);

    return root;
}

TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
    std::unordered_map<int, int> inorderMap;
    for (int i = 0; i < inorder.size(); ++i) {
        inorderMap[inorder[i]] = i;
    }
    return buildTreeHelper(preorder, 0, preorder.size() - 1,
                           inorder, 0, inorder.size() - 1, inorderMap);
}

Explanation:

• Mapping Inorder Indices: A hash map is used to store the indices of values in the inorder traversal, allowing for quick lookups when dividing the tree into left and right subtrees. • Recursive Construction: The tree is constructed recursively by determining the root node from the preorder traversal and dividing the inorder traversal into left and right subtrees. • Handling Subtrees: The left and right subtrees are recursively constructed using the corresponding segments of the preorder and inorder traversals.

Applications:

• Tree Reconstruction: Building a binary tree from traversal data, which is common in parsing tasks, compilers, and data reconstruction. • Tree Transformation: Converting trees into different forms, such as linked lists, strings, or arrays, for use in various algorithms and data processing tasks.

Pattern 8: Advanced Binary Tree Problems

Overview: Advanced binary tree problems often combine multiple concepts and require deep insights into the structure and properties of binary trees. These problems may involve complex operations such as finding the maximum path sum, serializing and deserializing trees, or placing binary tree cameras to monitor nodes. They typically require a mix of traversal techniques, dynamic programming, and advanced recursion.

Key Points:

  • Maximum Path Sum: Finding the path in a binary tree where the sum of node values is the highest. This path may start and end at any node.
  • Serialization and Deserialization: Converting a binary tree into a format that can be stored or transmitted and then reconstructing the tree from that format.
  • Binary Tree Cameras: Placing cameras in the tree to monitor all nodes with the fewest number of cameras, usually involves dynamic programming or greedy approaches.
  • Combination of Concepts: Problems in this category often require combining basic tree operations with more advanced techniques like dynamic programming, backtracking, or even graph algorithms.

Problems:

Code Example (Binary Tree Maximum Path Sum):

// Binary Tree Maximum Path Sum in C++
#include <algorithm>

int maxPathSumHelper(TreeNode* root, int& maxSum) {
    if (!root) return 0;
    
    int leftGain = std::max(maxPathSumHelper(root->left, maxSum), 0);
    int rightGain = std::max(maxPathSumHelper(root->right, maxSum), 0);
    
    int priceNewPath = root->val + leftGain + rightGain;
    
    maxSum = std::max(maxSum, priceNewPath);
    
    return root->val + std::max(leftGain, rightGain);
}

int maxPathSum(TreeNode* root) {
    int maxSum = INT_MIN;
    maxPathSumHelper(root, maxSum);
    return maxSum;
}

Explanation:

• Recursive Helper Function: The helper function calculates the maximum gain from the left and right subtrees. It ensures that if a subtree’s gain is negative, it is discarded (i.e., treated as 0). • Calculating the Path Sum: The path sum for the current node is calculated by adding the node’s value to the maximum gains from the left and right subtrees. • Updating the Maximum Sum: The global maximum path sum is updated if the current path sum is higher than the previously recorded maximum. • Return Value: The function returns the maximum gain that can be obtained by continuing the path through either the left or right subtree.

Applications:

• Optimal Substructure Problems: Advanced binary tree problems often require finding optimal substructures, such as the maximum path sum that can be formed by combining multiple subtrees. • Data Compression and Transmission: Serialization and deserialization are key in transmitting tree data over networks or storing it in a compressed format. • Security and Monitoring: Placing cameras or other monitoring devices efficiently in hierarchical structures, ensuring minimal coverage overlaps.

You May Also Enjoy

Backtracking : A Comprehensive Guide

2 minute read

Published:

Backtracking is a powerful algorithmic technique for solving problems related to permutations, combinations, and subsets. The essence of backtracking lies in exploring all potential solutions and then backtracking by undoing the last decision and trying the next possibility. Below is a generalized template for backtracking that can be adapted to a variety of problems like subsets, permutations, and combinations.

Dynamic Programming Pattern: Knapsack-like

3 minute read

Published:

This pattern has two sub-patterns namely, 0-1 Knapsack and Unbounded Knapsack. Together, the type of problems that match these patterns are called “Knapsack-like” problems.

841: Keys and Rooms

2 minute read

Published:

You are given n rooms labeled from 0 to n - 1, and all the rooms are locked except for room 0. Your goal is to visit all the rooms, but you cannot enter a locked room without having its key.

802: Find Eventual Safe States

2 minute read

Published:

Given a directed graph with n nodes labeled from 0 to n - 1, we need to identify all the safe nodes in the graph. A node is considered safe if every possible path starting from that node leads to a terminal node or another safe node. A terminal node is defined as a node that has no outgoing edges.