forked from bishweashwarsukla/hactoberfest2022
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDetermine if a binary tree is height-balanced?
79 lines (66 loc) · 1.77 KB
/
Determine if a binary tree is height-balanced?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/* Java program to determine if binary tree is
height balanced or not */
/* A binary tree node has data, pointer to left child,
and a pointer to right child */
class Node {
int data;
Node left, right;
Node(int d)
{
data = d;
left = right = null;
}
}
class BinaryTree {
Node root;
/* Returns true if binary tree with root as root is
* height-balanced */
boolean isBalanced(Node node)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */
/* If tree is empty then return true */
if (node == null)
return true;
/* Get the height of left and right sub trees */
lh = height(node.left);
rh = height(node.right);
if (Math.abs(lh - rh) <= 1 && isBalanced(node.left)
&& isBalanced(node.right))
return true;
/* If we reach here then tree is not height-balanced
*/
return false;
}
/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */
/* The function Compute the "height" of a tree. Height
is the number of nodes along the longest path from
the root node down to the farthest leaf node.*/
int height(Node node)
{
/* base case tree is empty */
if (node == null)
return 0;
/* If tree is not empty then height = 1 + max of
left height and right heights */
return 1
+ Math.max(height(node.left),
height(node.right));
}
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.left.left.left = new Node(8);
if (tree.isBalanced(tree.root))
System.out.println("Tree is balanced");
else
System.out.println("Tree is not balanced");
}
}
// This code has been contributed by Mayank
// Jaiswal(mayank_24)