Vertical order traversal

Dec 18, 2024 • 5 mins read

Problem Overview

The problem we are addressing is "Vertical Order Traversal of a Binary Tree" from LeetCode, with the URL provided. The task requires traversing a binary tree vertically and returns nodes in a specific order based on their position in the tree. The solution requires the understanding and manipulation of binary trees using custom ordering criteria.

Understanding the Problem

This problem involves outputting the nodes of a binary tree in a specific vertical order. Specifically, for each node at position (r, c) (where r is the row and c is the column index), the following constraints are followed:

Nodes with the same column are grouped together.
If two nodes are in the same row and column, they are ordered by node value.
Columns are processed from left to right.

Therefore, for a typical binary tree, nodes are output as grouped vertically and then ordered by their individual node values.

Key DSA Concepts and Theory

Binary Tree

A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. Binary trees are essential in various contexts like expression parsing, search algorithms, and binary heaps.

Tree Traversal

Tree traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. Tree traversal methods are categorized mainly into:

Pre-order Traversal: Visit the root node, traverse the left subtree, then traverse the right subtree.
In-order Traversal: Traverse the left subtree, visit the root node, and then traverse the right subtree.
Post-order Traversal: Traverse the left subtree, then the right subtree, and finally visit the root node.
Level-order Traversal: Visit nodes level by level from top to bottom.

Use of Data Structures

To solve this problem efficiently, we will utilize:

Containers to hold nodes' values with their vertical positions, specifically dictionaries or maps in a language-appropriate manner, to facilitate column-wise organization of nodes.
Priority queues (or min-heaps) can be employed to maintain and retrieve the smallest or highest-priority elements when necessary, although this problem primarily requires sorting for ordering.

Solution Approach

The solution involves a breadth-first traversal (leveraging a queue) while maintaining the horizontal distance for each node.

C++ Solution:

#include <vector>
#include <map>
#include <queue>
#include <tuple>
#include <algorithm>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

vector<vector<int>> verticalTraversal(TreeNode* root) {
    // Map to hold nodes according to column and row (column -> row -> multiset of nodes)
    map<int, map<int, multiset<int>>> nodes;
    // Queue to perform the BFS
    queue<tuple<TreeNode*, int, int>> q; // node, row, column
    q.push({root, 0, 0});
    
    while (!q.empty()) {
        auto [node, row, col] = q.front();
        q.pop();
        if (node) {
            nodes[col][row].insert(node->val);
            if (node->left) q.push({node->left, row + 1, col - 1});
            if (node->right) q.push({node->right, row + 1, col + 1});
        }
    }
    
    vector<vector<int>> output;
    for (auto p : nodes) {
        vector<int> col;
        for (auto q : p.second) {
            col.insert(col.end(), q.second.begin(), q.second.end());
        }
        output.push_back(col);
    }
    return output;
}

Java Solution:

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map = new TreeMap<>();
        Queue<Tuple> queue = new LinkedList<>();
        queue.offer(new Tuple(root, 0, 0));
        
        while (!queue.isEmpty()) {
            Tuple tuple = queue.poll();
            TreeNode node = tuple.node;
            int row = tuple.row;
            int col = tuple.column;
            
            map.putIfAbsent(col, new TreeMap<>());
            map.get(col).putIfAbsent(row, new PriorityQueue<>());
            map.get(col).get(row).offer(node.val);
            
            if (node.left != null) {
                queue.offer(new Tuple(node.left, row + 1, col - 1));
            }
            if (node.right != null) {
                queue.offer(new Tuple(node.right, row + 1, col + 1));
            }
        }
        
        List<List<Integer>> output = new ArrayList<>();
        for (TreeMap<Integer, PriorityQueue<Integer>> nestedMap : map.values()) {
            List<Integer> colNodes = new ArrayList<>();
            for (PriorityQueue<Integer> nodes : nestedMap.values()) {
                while (!nodes.isEmpty()) {
                    colNodes.add(nodes.poll());
                }
            }
            output.add(colNodes);
        }
        return output;
    }

    private class Tuple {
        TreeNode node;
        int row, column;
        
        Tuple(TreeNode n, int r, int c) {
            node = n;
            row = r;
            column = c;
        }
    }
}

Detailed Steps:

Data Structures: Use a TreeMap in Java (or map in C++) to store nodes keyed by their vertical and then horizontal positions.
BFS Traversal: Start with the root node, and utilize a queue to perform a BFS traversal, storing node values in the map as per their respective positions.
Sorting: Ensure nodes in the same horizontal and vertical paths are ordered.
Construction of Output: Extract the values from the map into a list of lists for the final output.

Time and Space Complexity Analysis

Time Complexity: O(N log N), where N is the number of nodes in the tree. This time complexity arises from the traversal of nodes and sorting of nodes within the same horizontal position.
Space Complexity: O(N), the space needed to store the node values in the data structure.

Additional Resources and References

Learn more about Binary Trees at GeeksforGeeks
PriorityQueue in Java: Java Documentation
Understanding Map and Multiset in C++ STL: C++ Reference

These resources provide a foundational understanding of the concepts and data structures used in the coding examples, offering you a deeper exploration path to further solidify these key areas.

Terms & Conditions Privacy Policy Refund Policy