Skip to main content

Check if a given BST is height balanced

Check if a given BST height balanced

Here given code implementation process.

//C Program 
//Check if a given BST is height balanced
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Search Tree node
struct Node
{
  int data;
  struct Node *left,*right; 
};

//Adding a new node in binary search tree
void add( struct Node **root, int data)
{
  //Create a dynamic node of binary search tree 
  struct Node *new_node = (struct Node *)malloc(sizeof(struct Node ));

  if(new_node!=NULL)
  {
    //Set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL;//Initially node right-pointer is NULL

    if(*root == NULL)
    {
      //When adds a first node in binary tree
      *root = new_node;
    }
    else
    {
      struct Node *find = *root;
      //iterate binary tree and add new node to proper position
      while(find != NULL)
      {
        if(find -> data > data)
        { 
          if(find->left==NULL)
          {
            find->left = new_node;
            break;
          }
          else
          { //visit left sub-tree
            find = find->left;
          }
        }
        else
        {
          if(find->right == NULL)
          {
            find->right = new_node;
            break;
          }
          else
          {
            //visit right sub-tree
            find = find->right;
          }
        }
      }
    }
  }else
  {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }

}

int height(struct Node*root ,int *status)
{
  if(root != NULL && *status==1)
  {
    
    int a = height(root->left,status);
    int b = height(root->right,status);

    if(a>b)
    {
      if(a-1!=b)
      {
        *status=0;
      }
      return a+1;
    }
    else
    {
      if(b!=a && b-1!=a)
      {
        *status=0;
      }
      return b+1;
    }
  }
   return 0;
}
void inorder(struct Node*root)
{
  if(root!=NULL)
  {
    
    inorder(root->left);
    printf("%3d ",root->data );
    inorder(root->right);
  }
}
void check_height(struct Node*root)
{
  if(root != NULL)
  {
    int status=1;
    inorder(root);
    printf("\n");
    height(root,&status);

    if(status==1)
    {
      printf(" Height Balanced BST\n");
    }
    else
    {
      printf(" Not Height Balanced BST\n");
    }
    printf("\n");
  }
 
}

int main(){
    
  struct Node*root = NULL;

  //Add nodes in binary search tree
  /*
             5
           /    \
          3      9
         / \     
        1   4      
       / \     
      -3  2          


  */                


    add(&root,5); 
    add(&root,3); 
    add(&root,9); 
    add(&root,1); 
    add(&root,4);
    add(&root,-3); 
    add(&root,2); 


  check_height(root);

/*
             5
           /    \
          3      9
         / \     / 
        1   4   8   
       / \     
      -3  2          

*/
  add(&root,8); 

  check_height(root);

  return 0;
}

Output

-3  1  2  3  4  5  9  
 Not Height Balanced BST

-3  1  2  3  4  5  8  9  
 Height Balanced BST
/*
 C++ Program
 Check if a given BST is height balanced
*/

#include<iostream>

using namespace std;
class Node {
public:
  int data;
  Node *left;
  Node *right;
  Node(int value) {
    this->data = value;
    this->left = NULL;
    this->right = NULL;
  }
};
class BinarySearchTree {
  public:
  Node *root;
  bool status;
  BinarySearchTree() {
    this->root = NULL;
    this->status = false;
  }
  void add(int value) {
    Node *new_node = new Node(value);
    if (new_node != NULL) {
      if (this->root == NULL) {
        this->root = new_node;
      } else {
        Node *find = this->root;
        while (find != NULL) {
          if (find->data >= value) {
            if (find->left == NULL) {
              find->left = new_node;
              break;
            } else {
              find = find->left;
            }
          } else {
            if (find->right == NULL) {
              find->right = new_node;
              break;
            } else {
              find = find->right;
            }
          }
        }
      }
    } else {
      cout << "\nMemory Overflow\n";
    }
  }
  int height(Node *head) {
    if (head != NULL && this->status == true) {
      int a = this->height(head->left);
      int b = this->height(head->right);
      if (a > b) {
        if (a - 1 != b) {
          this->status = false;
        }
        return a + 1;
      } else {
        if (b != a && b - 1 != a) {
          this->status = false;
        }
        return b + 1;
      }
    }
    return 0;
  }
  void inorder(Node *head) {
    if (head != NULL) {
      this->inorder(head->left);
      cout << "  " << head->data;
      this->inorder(head->right);
    }
  }
  void check_height() {
    if (this->root != NULL) {
      this->status = true;
      this->inorder(this->root);
      cout << ("\n");
      this->height(this->root);
      if (this->status == true) {
        cout << " Height Balanced BST\n";
      } else {
        cout << " Not Height Balanced BST\n";
      }
      cout << ("\n");
    }
  }
};
int main() {
  BinarySearchTree obj ;
  /*
             5
           /    \
          3      9
         / \     
        1   4      
       / \     
      -3  2          


  */ 
  obj.add(5);
  obj.add(3);
  obj.add(9);
  obj.add(1);
  obj.add(4);
  obj.add(-3);
  obj.add(2);
  obj.check_height();
  obj.add(8);
  /*
             5
           /    \
          3      9
         / \    /
        1   4  8   
       / \     
      -3  2          


  */ 
  obj.check_height();
  return 0;
}

Output

-3  1  2  3  4  5  9  
 Not Height Balanced BST

-3  1  2  3  4  5  8  9  
 Height Balanced BST
//Java program
//Check if a given BST is height balanced

class Node {
  public int data;
  public Node left;
  public Node right;

  public Node(int value) {
    data = value;
    left = null;
    right = null;
  }
}
public class BinarySearchTree {


  public Node root;
  public boolean status;
  BinarySearchTree() {
    root = null;
    status = false;

  }
  //insert a node in BST
  public void add(int value) {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node(value);

    if (new_node != null) {
      if (root == null) {
        //When adds a first node in binary tree
        root = new_node;
      } else {
        Node find = root;

        //add new node to proper position
        while (find != null) {
          if (find.data >= value) {
            if (find.left == null) {
              find.left = new_node;
              break;
            } else {
              //visit left sub-tree
              find = find.left;
            }
          } else {
            if (find.right == null) {
              find.right = new_node;
              break;
            } else {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    } else {
      System.out.print("\nMemory Overflow\n");
    }
  }
  public int height(Node head) {
    if (head != null && this.status == true) {

      int a = height(head.left);
      int b = height(head.right);

      if (a > b) {
        if (a - 1 != b) {
          this.status = false;
        }
        return a + 1;
      } else {
        if (b != a && b - 1 != a) {
          this.status = false;
        }
        return b + 1;
      }
    }
    return 0;
  }
  public void inorder(Node head) {
    if (head != null) {

      inorder(head.left);
      System.out.print("  " + head.data);
      inorder(head.right);
    }
  }
  public void check_height() {
    if (this.root != null) {
      this.status = true;
      inorder(this.root);
      System.out.print("\n");
      height(root);

      if (status == true) {
        System.out.print(" Height Balanced BST\n");
      } else {
        System.out.print(" Not Height Balanced BST\n");
      }
      System.out.print("\n");
    }

  }
  public static void main(String[] args) {

    BinarySearchTree obj = new BinarySearchTree();

    //Add nodes in binary search tree
    /*
               5
             /    \
            3      9
           / \     
          1   4      
         / \     
        -3  2          


    */


    obj.add(5);
    obj.add(3);
    obj.add(9);
    obj.add(1);
    obj.add(4);
    obj.add(-3);
    obj.add(2);


    obj.check_height();

    /*
                 5
               /    \
              3      9
             / \     / 
            1   4   8   
           / \     
          -3  2          

    */
    obj.add(8);

    obj.check_height();


  }
}

Output

-3  1  2  3  4  5  9  
 Not Height Balanced BST

-3  1  2  3  4  5  8  9  
 Height Balanced BST
//C# program
//Check if a given BST is height balanced
using System;
public class Node {
	public int data;
	public Node left;
	public Node right;

	public Node(int value) {
		data = value;
		left = null;
		right = null;
	}
}
public class BinarySearchTree {


	public Node root;
	public Boolean status;
	BinarySearchTree() {
		root = null;
		status = false;

	}
	//insert a node in BST
	public void add(int value) {
		//Create a dynamic node of binary search tree 
		Node new_node = new Node(value);

		if (new_node != null) {
			if (root == null) {
				//When adds a first node in binary tree
				root = new_node;
			} else {
				Node find = root;

				//add new node to proper position
				while (find != null) {
					if (find.data >= value) {
						if (find.left == null) {
							find.left = new_node;
							break;
						} else {
							//visit left sub-tree
							find = find.left;
						}
					} else {
						if (find.right == null) {
							find.right = new_node;
							break;
						} else {
							//visit right sub-tree
							find = find.right;
						}
					}
				}
			}
		} else {
			Console.Write("\nMemory Overflow\n");
		}
	}
	public int height(Node head) {
		if (head != null && this.status == true) {

			int a = height(head.left);
			int b = height(head.right);

			if (a > b) {
				if (a - 1 != b) {
					this.status = false;
				}
				return a + 1;
			} else {
				if (b != a && b - 1 != a) {
					this.status = false;
				}
				return b + 1;
			}
		}
		return 0;
	}
	public void inorder(Node head) {
		if (head != null) {

			inorder(head.left);
			Console.Write("  " + head.data);
			inorder(head.right);
		}
	}
	public void check_height() {
		if (this.root != null) {
			this.status = true;
			inorder(this.root);
			Console.Write("\n");
			height(root);

			if (status == true) {
				Console.Write(" Height Balanced BST\n");
			} else {
				Console.Write(" Not Height Balanced BST\n");
			}
			Console.Write("\n");
		}

	}
	public static void Main(String[] args) {

		BinarySearchTree obj = new BinarySearchTree();

		//Add nodes in binary search tree
		/*
               5
             /    \
            3      9
           / \     
          1   4      
         / \     
        -3  2          


    */


		obj.add(5);
		obj.add(3);
		obj.add(9);
		obj.add(1);
		obj.add(4);
		obj.add(-3);
		obj.add(2);


		obj.check_height();

		/*
                 5
               /    \
              3      9
             / \     / 
            1   4   8   
           / \     
          -3  2          

    */
		obj.add(8);

		obj.check_height();


	}
}

Output

-3  1  2  3  4  5  9  
 Not Height Balanced BST

-3  1  2  3  4  5  8  9  
 Height Balanced BST
# Python 3 Program
# Check if a given BST is height balanced

class Node :

  def __init__(self, value) :
    self.data = value
    self.left = None
    self.right = None
  

class BinarySearchTree :

  def __init__(self) :
    self.root = None
    self.status = False
  
  def add(self, value) :
    new_node = Node(value)
    if (new_node != None) :
      if (self.root == None) :
        self.root = new_node
      else :
        find = self.root
        while (find != None) :
          if (find.data >= value) :
            if (find.left == None) :
              find.left = new_node
              break
            else :
              find = find.left
            
          else :
            if (find.right == None) :
              find.right = new_node
              break
            else :
              find = find.right
            
          
        
      
    else :
      print("\nMemory Overflow\n")
    
  
  def height(self, head) :
    if (head != None and self.status == True) :
      a = self.height(head.left)
      b = self.height(head.right)
      if (a > b) :
        if (a - 1 != b) :
          self.status = False
        
        return a + 1
      else :
        if (b != a and b - 1 != a) :
          self.status = False
        
        return b + 1
      
    
    return 0
  
  def inorder(self, head) :
    if (head != None) :
      self.inorder(head.left)
      print( head.data,end="  ")
      self.inorder(head.right)
    
  
  def check_height(self) :
    if (self.root != None) :
      self.status = True
      self.inorder(self.root)
      print()
      self.height(self.root)
      if (self.status == True) :
        print(" Height Balanced BST\n")
      else :
        print(" Not Height Balanced BST\n")
      
   
    
  
def main() :
  obj = BinarySearchTree()
  obj.add(5)
  obj.add(3)
  obj.add(9)
  obj.add(1)
  obj.add(4)
  obj.add(-3)
  obj.add(2)
  obj.check_height()
  obj.add(8)
  obj.check_height()
  

if __name__ == "__main__":
  main()

Output

-3  1  2  3  4  5  9  
 Not Height Balanced BST

-3  1  2  3  4  5  8  9  
 Height Balanced BST
# Ruby Program
# Check if a given BST is height balanced

class Node 
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(value) 
		@data = value
		@left = nil
		@right = nil
	end
end

class BinarySearchTree 
	attr_reader :root, :status
	attr_accessor :root, :status
	def initialize() 
		@root = nil
		@status = false
	end
	def add(value) 
		new_node = Node.new(value)
		if (new_node != nil) 
			if (@root == nil) 
				@root = new_node
			else 
				find = @root
				while (find != nil) 
					if (find.data >= value) 
						if (find.left == nil) 
							find.left = new_node
							break
						else 
							find = find.left
						end
					else 
						if (find.right == nil) 
							find.right = new_node
							break
						else 
							find = find.right
						end
					end
				end
			end
		else 
			print("\nMemory Overflow\n")
		end
	end
	def height(head) 
		if (head != nil and self.status == true) 
			a = self.height(head.left)
			b = self.height(head.right)
			if (a > b) 
				if (a - 1 != b) 
					self.status = false
				end
				return a + 1
			else 
				if (b != a and b - 1 != a) 
					self.status = false
				end
				return b + 1
			end
		end
		return 0
	end
	def inorder(head) 
		if (head != nil) 
			self.inorder(head.left)
			print("  ", head.data)
			self.inorder(head.right)
		end
	end
	def check_height() 
		if (self.root != nil) 
			self.status = true
			self.inorder(self.root)
			print("\n")
			self.height(@root)
			if (@status == true) 
				print(" Height Balanced BST\n")
			else 
				print(" Not Height Balanced BST\n")
			end
			print("\n")
		end
	end
end
def main() 
	obj = BinarySearchTree.new()
	obj.add(5)
	obj.add(3)
	obj.add(9)
	obj.add(1)
	obj.add(4)
	obj.add(-3)
	obj.add(2)
	obj.check_height()
	obj.add(8)
	obj.check_height()
end

main()

Output

-3  1  2  3  4  5  9  
 Not Height Balanced BST

-3  1  2  3  4  5  8  9  
 Height Balanced BST
<?php
/*
 Php Program
 Check if a given BST is height balanced
*/

class Node {
  public $data;
  public $left;
  public $right;

  function __construct($value) {
    $this->data = $value;
    $this->left = null;
    $this->right = null;
  }
}
class BinarySearchTree {
  public $root;
  public $status;

  function __construct() {
    $this->root = null;
    $this->status = false;
  }
  public  function add($value) {
    $new_node = new Node($value);
    if ($new_node != null) {
      if ($this->root == null) {
        $this->root = $new_node;
      } else {
        $find = $this->root;
        while ($find != null) {
          if ($find->data >= $value) {
            if ($find->left == null) {
              $find->left = $new_node;
              break;;
            } else {
              $find = $find->left;
            }
          } else {
            if ($find->right == null) {
              $find->right = $new_node;
              break;;
            } else {
              $find = $find->right;
            }
          }
        }
      }
    } else {
      echo("\nMemory Overflow\n");
    }
  }
  public  function height($head) {
    if ($head != null && $this->status == true) {
      $a = $this->height($head->left);
      $b = $this->height($head->right);
      if ($a > $b) {
        if ($a - 1 != $b) {
          $this->status = false;
        }
        return $a + 1;
      } else {
        if ($b != $a && $b - 1 != $a) {
          $this->status = false;
        }
        return $b + 1;
      }
    }
    return 0;
  }
  public  function inorder($head) {
    if ($head != null) {
      $this->inorder($head->left);
      echo("  ". $head->data);
      $this->inorder($head->right);
    }
  }
  public  function check_height() {
    if ($this->root != null) {
      $this->status = true;
      $this->inorder($this->root);
      echo("\n");
      $this->height($this->root);
      if ($this->status == true) {
        echo(" Height Balanced BST\n");
      } else {
        echo(" Not Height Balanced BST\n");
      }
      echo("\n");
    }
  }
}
function main() {
  $obj = new BinarySearchTree();
  /*
             5
           /    \
          3      9
         / \     
        1   4      
       / \     
      -3  2          


  */ 
  $obj->add(5);
  $obj->add(3);
  $obj->add(9);
  $obj->add(1);
  $obj->add(4);
  $obj->add(-3);
  $obj->add(2);
  $obj->check_height();
  $obj->add(8);
  /*
             5
           /    \
          3      9
         / \    /
        1   4  8   
       / \     
      -3  2          


  */ 
  $obj->check_height();
}
main();

Output

-3  1  2  3  4  5  9  
 Not Height Balanced BST

-3  1  2  3  4  5  8  9  
 Height Balanced BST
/*
 Node Js Program
 Check if a given BST is height balanced
*/

class Node {

	constructor(value) {
		this.data = value;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree {
	
	constructor() {
		this.root = null;
		this.status = false;
	}
	add(value) {
		var new_node = new Node(value);
		if (new_node != null) {
			if (this.root == null) {
				this.root = new_node;
			} else {
				var find = this.root;
				while (find != null) {
					if (find.data >= value) {
						if (find.left == null) {
							find.left = new_node;
							break;;
						} else {
							find = find.left;
						}
					} else {
						if (find.right == null) {
							find.right = new_node;
							break;;
						} else {
							find = find.right;
						}
					}
				}
			}
		} else {
			process.stdout.write("\nMemory Overflow\n");
		}
	}
	height(head) {
		if (head != null && this.status == true) {
			var a = this.height(head.left);
			var b = this.height(head.right);
			if (a > b) {
				if (a - 1 != b) {
					this.status = false;
				}
				return a + 1;
			} else {
				if (b != a && b - 1 != a) {
					this.status = false;
				}
				return b + 1;
			}
		}
		return 0;
	}
	inorder(head) {
		if (head != null) {
			this.inorder(head.left);
			process.stdout.write("  " + head.data);
			this.inorder(head.right);
		}
	}
	check_height() {
		if (this.root != null) {
			this.status = true;
			this.inorder(this.root);
			process.stdout.write("\n");
			this.height(this.root);
			if (this.status == true) {
				process.stdout.write(" Height Balanced BST\n");
			} else {
				process.stdout.write(" Not Height Balanced BST\n");
			}
			process.stdout.write("\n");
		}
	}
}

function main() {
	
	var obj = new BinarySearchTree();
	/*
             5
           /    \
          3      9
         / \     
        1   4      
       / \     
      -3  2          


    */ 
	obj.add(5);
	obj.add(3);
	obj.add(9);
	obj.add(1);
	obj.add(4);
	obj.add(-3);
	obj.add(2);

	obj.check_height();

	obj.add(8);
	/*
             5
           /    \
          3      9
         / \    / 
        1   4  8    
       / \     
      -3  2          


    */ 
	obj.check_height();
}

main();

Output

-3  1  2  3  4  5  9  
 Not Height Balanced BST

-3  1  2  3  4  5  8  9  
 Height Balanced BST
/*
 Swift 4 Program
 Check if a given BST is height balanced
*/

class Node {
  var data: Int;
  var left: Node? ;
  var right: Node? ;
  init(_ value: Int) {
    self.data = value;
    self.left = nil;
    self.right = nil;
  }
}
class BinarySearchTree {
  var root: Node? ;
  var status: Bool;
  init() {
    self.root = nil;
    self.status = false;
  }
  func add(_ value: Int) {
    let new_node: Node? = Node(value);
    if (new_node != nil) {
      if (self.root == nil) {
        self.root = new_node;
      } else {
        var find: Node? = self.root;
        while (find != nil) {
          if (find!.data >= value) {
            if (find!.left == nil) {
              find!.left = new_node;
              break;
            } else {
              find = find!.left;
            }
          } else {
            if (find!.right == nil) {
              find!.right = new_node;
              break;
            } else {
              find = find!.right;
            }
          }
        }
      }
    } else {
      print("\nMemory Overflow\n");
    }
  }
  func height(_ head: Node? ) -> Int {
    if (head != nil && self.status == true) {
      let a: Int = self.height(head!.left);
      let b: Int = self.height(head!.right);
      if (a > b) {
        if (a - 1 != b) {
          self.status = false;
        }
        return a + 1;
      } else {
        if (b != a && b - 1 != a) {
          self.status = false;
        }
        return b + 1;
      }
    }
    return 0;
  }
  func inorder(_ head: Node? ) {
    if (head != nil) {
      self.inorder(head!.left);
      print(head!.data, terminator:"  ");
      self.inorder(head!.right);
    }
  }
  func check_height() {
    if (self.root != nil) {
      self.status = true;
      self.inorder(self.root);
      print();


      var _ = self.height(self.root);

      if (self.status == true) {
        print(" Height Balanced BST\n");
      } else {
        print(" Not Height Balanced BST\n");
      }
      
    }
  }
}
func main() {
  let obj: BinarySearchTree = BinarySearchTree();
  /*
           5
         /    \
        3      9
       / \     
      1   4      
     / \     
    -3  2          


  */ 
  obj.add(5);
  obj.add(3);
  obj.add(9);
  obj.add(1);
  obj.add(4);
  obj.add(-3);
  obj.add(2);
  obj.check_height();
  obj.add(8);
  /*
           5
         /    \
        3      9
       / \    / 
      1   4  8    
     / \     
    -3  2          


  */ 
  obj.check_height();
}
main();

Output

-3  1  2  3  4  5  9  
 Not Height Balanced BST

-3  1  2  3  4  5  8  9  
 Height Balanced BST




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment