Binary tree lookup

A Binary tree is a tree with two nodes left node, right node and root node . The root node is a top most node in the tree.

Write a program to print all the paths in binary tree using Pre-order traversal.

source Code

package com.dsacode.Algorithm.divideconquer;
 
class TreeNodePrintAll {
    public TreeNodePrintAll left;
    public TreeNodePrintAll right;
    int data;
 
    public TreeNodePrintAll(int data) {
        this.left = null;
        this.right = null;
        this.data = data;
    }
 
    @Override
    public String toString() {
        return data + " ";
    }
 
}
 
public class PrintAllPath {
 
    TreeNodePrintAll root;
 
    void printTree(TreeNodePrintAll node) {
        if (node == null)
            return;
 
        printTree(node.left);
        System.out.print(node + "  ");
        printTree(node.right);
    }
 
    void printAllPath(TreeNodePrintAll root, int[] arr, int level) {
 
        if (root == null)
            return;
 
        arr[level] = root.data;
 
        if (root.left == null && root.right == null) {
            printPath(arr, 0, level);
            return;
        }
 
        printAllPath(root.left, arr, level + 1);
        printAllPath(root.right, arr, level + 1);
 
    }
 
    private void printPath(int[] arr, int l, int level) {
 
        for (int i = l; i <= level; i++)
            System.out.print(arr[i] + ", ");
        System.out.println();
 
    }
 
    int height(TreeNodePrintAll t) {
        if (t == null)
            return -1;
        else
            return 1 + Math.max(height(t.left), height(t.right));
    }
 
    public static void main(String[] args) {
        PrintAllPath b = new PrintAllPath();
 
        b.root = new TreeNodePrintAll(20);
        b.root.left = new TreeNodePrintAll(8);
        b.root.right = new TreeNodePrintAll(22);
        b.root.left.left = new TreeNodePrintAll(4);
        b.root.left.right = new TreeNodePrintAll(12);
        b.root.left.right.left = new TreeNodePrintAll(10);
        b.root.left.right.right = new TreeNodePrintAll(14);
 
        System.out.print("All Binary Tree Values: ");
        b.printTree(b.root);
        System.out.println();
 
        int[] arr = new int[b.height(b.root) + 1];
 
        System.out.println("\nPrint all the Tree paths: ");
        b.printAllPath(b.root, arr, 0);
 
    }
 
}

Output

All Binary Tree Values: 4   8   10   12   14   20   22  
 
Print all the Tree paths:
20, 8, 4
20, 8, 12, 10
20, 8, 12, 14
20, 22

Algorithm Explanation

	Display the data part of root element (or current element)
	Traverse the left subtree by recursively calling the pre-order function.
	Traverse the right subtree by recursively calling the pre-order function.

Time Complexity

Reference

1. https://en.wikipedia.org/wiki/Binary_search_tree
2. http://cslibrary.stanford.edu/110/BinaryTrees.html