Posts Height Balanced Binary Tree
Post
Cancel

Height Balanced Binary Tree

PROBLEM DESCRIPTION

A binary tree is balanced if for each node in the tree, the difference between the height of its LST and RST is at most 1.

SOLUTION

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  public int heightBalancedBinaryTreeX(BinaryTree tree) {

    if(tree == null) return 0;
    
    int left = heightBalancedBinaryTreeX(tree.left);
    int right = heightBalancedBinaryTreeX(tree.right);

    return 1 + Math.max(left, right);
    
  }

  public boolean heightBalancedBinaryTree(BinaryTree tree) {

    if(tree == null) return true;

    int left = heightBalancedBinaryTreeX(tree.left);
    int right = heightBalancedBinaryTreeX(tree.right);
    
    return Math.abs(left-right) <= 1  && heightBalancedBinaryTree(tree.left) && heightBalancedBinaryTree(tree.right);
    
  }
This post is licensed under CC BY 4.0 by the author.