Program for finding maximum depth or height of a binary tree
/** * find height of the tree recursively */ public static int maxHeight() { return maxHeight(root, 0); } private static int maxHeight(Node node, int h) { if (node == null) { return h; } int lh = maxHeight(node.left, h + 1); int rh = maxHeight(node.right, h + 1); return (lh > rh) ? lh : rh; }
The complete program and sample run
package programs; public class BST { private static Node root = null; /** * find height of the tree recursively */ public static int maxHeight() { return maxHeight(root, 0); } private static int maxHeight(Node node, int h) { if (node == null) { return h; } int lh = maxHeight(node.left, h + 1); int rh = maxHeight(node.right, h + 1); return (lh > rh) ? lh : rh; } public static void main(String[] args) { createTree(); printTree(); System.out.println("Height " + maxHeight()); } private static void printTree() { print(root); } private static void print(Node node) { if (node != null) { print(node.left); System.out.print(node.data + " "); print(node.right); } } private static Node createTree() { root = new Node(50); root.left = new Node(40); root.left.left = new Node(30); root.left.right = new Node(45); root.left.left.left = new Node(25); root.left.left.left.left = new Node(20); root.left.left.left.left.left = new Node(15); root.right = new Node(70); root.right.left = new Node(60); root.right.right = new Node(90); root.right.right.left = new Node(80); root.right.right.left.right = new Node(85); return root; } } class Node { Node left; Node right; int data; public Node(int num) { this.data = num; } }
Output
No comments :
Post a Comment