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
Best Case | Average Case | Worst Case |
---|---|---|
– | O(log n) | O(n) |