Printing a binary tree in vertical order means printing the nodes of the tree such that nodes that appear in the same vertical line (when the tree is viewed from the side) are printed together. This involves organizing nodes based on their horizontal distance from the root of the tree.

Understanding Vertical Order Traversal

Objective: Given a binary tree, print its nodes in vertical order, which means nodes that share the same vertical line are grouped together.

Steps to Print a Binary Tree in Vertical Order

  1. Assign Horizontal Distance:
  • Start with the root node at horizontal distance 0.
  • For each left child, decrease the horizontal distance by 1.
  • For each right child, increase the horizontal distance by 1.
  1. Perform a Level-Order Traversal:
  • Use a breadth-first search (BFS) approach to traverse the tree level by level.
  • While traversing, keep track of nodes and their corresponding horizontal distances.
  1. Group Nodes by Vertical Line:
  • Use a data structure (like a dictionary or map) to group nodes by their horizontal distance.
  1. Sort and Print:
  • Sort the horizontal distances.
  • Print nodes corresponding to each horizontal distance in sorted order.

Example

Consider the following binary tree:

      1
     / \
    2   3
   / \   \
  4   5   6

Vertical Order:

  • Horizontal distance -2: 4
  • Horizontal distance -1: 2
  • Horizontal distance 0: 1, 5
  • Horizontal distance 1: 3
  • Horizontal distance 2: 6

Code Examples

1. Python

from collections import deque, defaultdict

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

def verticalOrder(root):
    if not root:
        return []

    # Dictionary to hold vertical order traversal
    column_table = defaultdict(list)
    # Queue for BFS: (node, horizontal_distance)
    queue = deque([(root, 0)])

    while queue:
        node, column = queue.popleft()
        if node is not None:
            column_table[column].append(node.value)
            if node.left:
                queue.append((node.left, column - 1))
            if node.right:
                queue.append((node.right, column + 1))

    # Extract the columns in sorted order
    sorted_columns = sorted(column_table.keys())
    return [column_table[column] for column in sorted_columns]

# Helper function to create a binary tree for testing
def create_binary_tree():
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.right = TreeNode(6)
    return root

# Example usage
root = create_binary_tree()
result = verticalOrder(root)
for column in result:
    print(column)

2. JavaScript

class TreeNode {
    constructor(value = 0, left = null, right = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

function verticalOrder(root) {
    if (!root) return [];

    let columnTable = new Map();
    let queue = [[root, 0]];

    while (queue.length) {
        let [node, column] = queue.shift();
        if (node !== null) {
            if (!columnTable.has(column)) {
                columnTable.set(column, []);
            }
            columnTable.get(column).push(node.value);
            if (node.left) queue.push([node.left, column - 1]);
            if (node.right) queue.push([node.right, column + 1]);
        }
    }

    let sortedColumns = Array.from(columnTable.keys()).sort((a, b) => a - b);
    return sortedColumns.map(column => columnTable.get(column));
}

// Helper function to create a binary tree for testing
function createBinaryTree() {
    let root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);
    root.right.right = new TreeNode(6);
    return root;
}

// Example usage
let root = createBinaryTree();
let result = verticalOrder(root);
result.forEach(column => console.log(column));

3. Java

import java.util.*;

class TreeNode {
    int value;
    TreeNode left, right;
    TreeNode(int value) {
        this.value = value;
        this.left = this.right = null;
    }
}

public class VerticalOrderTraversal {
    public static List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Map<Integer, List<Integer>> columnTable = new TreeMap<>();
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.add(new Pair<>(root, 0));

        while (!queue.isEmpty()) {
            Pair<TreeNode, Integer> p = queue.poll();
            TreeNode node = p.getKey();
            int column = p.getValue();

            if (!columnTable.containsKey(column)) {
                columnTable.put(column, new ArrayList<>());
            }
            columnTable.get(column).add(node.value);

            if (node.left != null) {
                queue.add(new Pair<>(node.left, column - 1));
            }
            if (node.right != null) {
                queue.add(new Pair<>(node.right, column + 1));
            }
        }

        result.addAll(columnTable.values());
        return result;
    }

    // Helper function to create a binary tree for testing
    public static TreeNode createBinaryTree() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = createBinaryTree();
        List<List<Integer>> result = verticalOrder(root);
        for (List<Integer> column : result) {
            System.out.println(column);
        }
    }
}

4. C++

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

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

vector<vector<int>> verticalOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;

    map<int, vector<int>> columnTable;
    queue<pair<TreeNode*, int>> queue;  // Pair of node and column index
    queue.push({root, 0});

    while (!queue.empty()) {
        auto [node, column] = queue.front();
        queue.pop();

        if (node) {
            columnTable[column].push_back(node->value);
            if (node->left) queue.push({node->left, column - 1});
            if (node->right) queue.push({node->right, column + 1});
        }
    }

    for (auto& [col, nodes] : columnTable) {
        result.push_back(nodes);
    }

    return result;
}

// Helper function to create a binary tree for testing
TreeNode* createBinaryTree() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);
    return root;
}

int main() {
    TreeNode* root = createBinaryTree();
    vector<vector<int>> result = verticalOrder(root);
    for (const auto& column : result) {
        for (int value : column) {
            cout << value << " ";
        }
        cout << endl;
    }

    return 0;
}

5. C

using System;
using System.Collections.Generic;

class TreeNode {
    public int Value;
    public TreeNode Left;
    public TreeNode Right;
    public TreeNode(int value) {
        Value = value;
        Left = Right = null;
    }
}

class Program {
    public static IList<IList<int>> VerticalOrder(TreeNode root) {
        var result = new List<IList<int>>();
        if (root == null) return result;

        var columnTable = new SortedDictionary<int, List<int>>();
        var queue = new Queue<(TreeNode node, int column)>();
        queue.Enqueue((root, 0));

        while (queue.Count > 0) {
            var (node, column) = queue.Dequeue();
            if (!columnTable.ContainsKey(column)) {
                columnTable[column] = new List<int>();
            }
            columnTable[column].Add(node.Value);

            if (node.Left != null) queue.Enqueue((node.Left, column - 1));
            if (node.Right != null) queue.Enqueue((node.Right, column + 1));
        }

        foreach (var column in columnTable.Values) {


 result.Add(column);
        }

        return result;
    }

    // Helper function to create a binary tree for testing
    public static TreeNode CreateBinaryTree() {
        TreeNode root = new TreeNode(1);
        root.Left = new TreeNode(2);
        root.Right = new TreeNode(3);
        root.Left.Left = new TreeNode(4);
        root.Left.Right = new TreeNode(5);
        root.Right.Right = new TreeNode(6);
        return root;
    }

    static void Main() {
        TreeNode root = CreateBinaryTree();
        var result = VerticalOrder(root);
        foreach (var column in result) {
            Console.WriteLine(string.Join(" ", column));
        }
    }
}

To print a binary tree in vertical order:

  1. Initialize a queue for BFS and a map to track nodes by their horizontal distance.
  2. Perform BFS and update the map with nodes and their horizontal distances.
  3. Sort the horizontal distances and retrieve the nodes in sorted order.
  4. Print the nodes for each vertical line.
See also  How do you calculate the sum of two integers?

The code examples in Python, JavaScript, Java, C++, and C# demonstrate how to achieve vertical order traversal of a binary tree using these steps.

facebookShare on Facebook
TwitterPost on X
FollowFollow us
PinterestSave

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *