Print Vertical Order Traversal of Binary Tree

Given a binary tree, the task is to print Vertical  Order Traversal of Binary Tree starting from the leftmost level to the rightmost level. The vertical traversal should print the nodes from top to bottom at each vertical line, and if multiple nodes pass through the same vertical line, they should be printed in the order they appear in the level-order traversal of the tree.

Code Flow for Print Vertical  Order Traversal of Binary Tree

Method: printVerticalOrder(Node node)

  • Purpose: This method prints the vertical order of a binary tree.

  • Step-by-step:

    • Null Check: If the input node is null, returns without doing anything.

    • Initial Setup:

      • A variable horizontalDistance is initialized to 0. This will help track the horizontal distance of each node from the root.

      • A TreeMap called verticalMap is used to store nodes in vertical lines. A TreeMap is chosen because it automatically keeps the keys (horizontal distances) in sorted order (from left to right).

    • Recursive Call: The method getVerticalOrder(node, horizontalDistance, verticalMap) is called to populate the verticalMap.

    • Print the Result: It iterates through the entries of verticalMap and prints the nodes at each vertical line (ordered by their horizontal distance).

Method: getVerticalOrder(Node node, int horizontalDistance, Map<Integer, List<Integer>> verticalMap)

  • Purpose: This method is a recursive function that traverses the binary tree and populates the verticalMap with the nodes at their respective horizontal distances.

  • Step-by-step:

    • Null Check: If the input node is null returns. This prevents further processing for null nodes.

    • Populate verticalMap:

      • If the verticalMap already contains the current horizontalDistance as a key, the current node's data (node.data) is added to the list of values associated with that horizontal distance.

      • If the verticalMap does not contain the key, a new entry is created with the horizontalDistance as the key and a new list containing the current node's data.

    • Recursive Calls:

      • Left Subtree: The method calls itself recursively for the left child of the current node, with the horizontalDistance decreased by 1 (horizontalDistance - 1).

      • Right Subtree: The method calls itself recursively for the right child of the current node, with the horizontalDistance increased by 1 (horizontalDistance + 1).

 

Let's see the code now

package org.wesome.dsalgo;

import lombok.Data;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.TreeMap;

@Data
class Node {
    int data;
    Node left, right;

    public Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

public class BinaryTree {
    Node root;


    public static void printVerticalOrder(Node node) {
        /*  If the input node is null, then returns*/
        if (Objects.isNull(node)) {
            System.out.println("BinaryTree.printVerticalOrder node is null");
            return;
        }
        /*  variable horizontalDistance is initialized to 0. This will track the horizontal distance of each node from the root. */
        var horizontalDistance = 0;
        /*  A TreeMap is used to store nodes in vertical lines. A TreeMap is chosen because it automatically keeps the keys ie horizontal distances in sorted order from left to right.    */
        Map<Integer, List<Integer>> verticalMap = new TreeMap<>();
        getVerticalOrder(node, horizontalDistance, verticalMap);

        for (Map.Entry<Integer, List<Integer>> integerListEntry : verticalMap.entrySet()) {
            System.out.println("Level " + integerListEntry.getKey() + " " + integerListEntry.getValue());
        }
    }

    private static void getVerticalOrder(Node node, int horizontalDistance, Map<Integer, List<Integer>> verticalMap) {
        /*  If the input node is null, returns. */
        if (Objects.isNull(node)) {
            System.out.println("BinaryTree.getVerticalOrder node is null");
            return;
        }
        /*  If the verticalMap already contains the current horizontalDistance as a key, the current node's data (node.data) is added to the list of values associated with that horizontal distance.   */
        if (verticalMap.containsKey(horizontalDistance)) {
            verticalMap.get(horizontalDistance).add(node.data);
        }
        /*  If the verticalMap does not contain the key, a new entry is created with the horizontalDistance as the key and a new list containing the current node's data.   */
        else {
            List<Integer> list = new ArrayList<>();
            list.add(node.data);
            verticalMap.put(horizontalDistance, list);
        }
        /*  recursively call the left child of the current node, with the horizontalDistance decreased by 1 (horizontalDistance - 1).    */
        getVerticalOrder(node.left, horizontalDistance - 1, verticalMap);
        /*  recursively call the right child of the current node, with the horizontalDistance increased by 1 (horizontalDistance + 1).    */
        getVerticalOrder(node.right, horizontalDistance + 1, verticalMap);
    }

    void insert(int data) {
        System.out.println("BinarySearchTree.insert data = " + data);
        root = insert(root, data);
    }

    Node insert(Node root, int data) {
        if (Objects.isNull(root)) {
            Node tempNode = new Node(data);
            return tempNode;
        }
        if (data > root.data) {
            root.right = insert(root.right, data);
        } else {
            root.left = insert(root.left, data);
        }
        return root;
    }
}
package org.wesome.dsalgo;

import org.junit.jupiter.api.Test;

public class BinaryTreeTest {

    @Test
    void testEmptyTree() {
        // Test for an empty tree (null root)
        BinaryTree tree = new BinaryTree();
        BinaryTree.printVerticalOrder(tree.root);
    }

    @Test
    void testSingleNodeTree() {
        // Test for a tree with a single node
        BinaryTree tree = new BinaryTree();
        tree.insert(10);
        BinaryTree.printVerticalOrder(tree.root);
    }

    @Test
    void testBalancedBinaryTree() {
        // Test for a balanced binary tree
        BinaryTree tree = new BinaryTree();
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        tree.insert(2);
        tree.insert(7);
        tree.insert(12);
        tree.insert(18);
        BinaryTree.printVerticalOrder(tree.root);
    }

    @Test
    void testUnbalancedBinaryTree() {
        // Test for an unbalanced binary tree (sorted order insertion creating a right-skewed tree)
        BinaryTree tree = new BinaryTree();
        tree.insert(10);
        tree.insert(20);
        tree.insert(30);
        tree.insert(40);
        tree.insert(50);
        BinaryTree.printVerticalOrder(tree.root);
    }

    @Test
    void testTreeWithNegativeValues() {
        // Test for a tree with negative values
        BinaryTree tree = new BinaryTree();
        tree.insert(-5);
        tree.insert(-3);
        tree.insert(-2);
        tree.insert(-1);
        tree.insert(-7);
        tree.insert(-4);
        BinaryTree.printVerticalOrder(tree.root);
    }

    @Test
    void testLargeTree() {
        // Test for a large tree with many nodes
        BinaryTree tree = new BinaryTree();
        for (int i = 1; i <= 1000; i++) {
            tree.insert(i);
        }
        BinaryTree.printVerticalOrder(tree.root);
    }

    @Test
    void testBalancedTree() {
        BinaryTree tree = new BinaryTree();
        Node root = new Node(10);
        root.left = new Node(5);
        root.right = new Node(15);
        root.left.left = new Node(2);
        root.left.right = new Node(7);
        root.right.left = new Node(12);
        root.right.right = new Node(18);
        BinaryTree.printVerticalOrder(tree.root);
    }


    @Test
    void testRightSkewedTree() {
        // Constructing the following tree:
        //          10
        //           \
        //            20
        //             \
        //              30
        //               \
        //                40
        //                 \
        //                  50
        BinaryTree tree = new BinaryTree();
        Node root = new Node(10);
        root.right = new Node(20);
        root.right.right = new Node(30);
        root.right.right.right = new Node(40);
        root.right.right.right.right = new Node(50);
        BinaryTree.printVerticalOrder(tree.root);
    }

    @Test
    void testTreeWithDuplicateValues() {
        // Constructing the following tree:
        //          1
        //       /    \
        //      1       1
        //     / \     / \
        //    1   1   1   1

        Node root = new Node(1);
        root.left = new Node(1);
        root.right = new Node(1);
        root.left.left = new Node(1);
        root.left.right = new Node(1);
        root.right.left = new Node(1);
        root.right.right = new Node(1);
        BinaryTree.printVerticalOrder(root);
    }

    @Test
    void testTreeBinaryTreeValues() {
        // Constructing the following tree:
        //       1
        //      / \
        //     2   3
        //    / \
        //   4   5
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        BinaryTree.printVerticalOrder(root);
    }
}
plugins {
    id("java")
    id("io.freefair.lombok") version "8.13"
}

group = "org.wesome.dsalgo"
version = "1.0-SNAPSHOT"

repositories {
    mavenCentral()
}

dependencies {
    testImplementation(platform("org.junit:junit-bom:5.10.0"))
    testImplementation("org.junit.jupiter:junit-jupiter")
}

tasks.test {
    useJUnitPlatform()
}

Complexity Analysis

Time Complexity

  • O(n) for the tree traversal.

  • O(n log n) for inserting nodes into the TreeMap.

Space Complexity

additional space used by the TreeMap is O(n).

follow us on

YouTube IconLinkedIn Icon