Binary search tree height

This is a discussion on Binary search tree height within the C Programming forums, part of the General Programming Boards category; I am trying to find the height of the BST, but unfortunately I get the number of elements in the ...

  1. #1
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62

    Binary search tree height

    I am trying to find the height of the BST, but unfortunately I get the number of elements in the BST

    Input: 1 2 3
    Output: height = 3

    Input : 1 2 3 4 5
    Output: height = 5

    Code:
    int height(node_ptr tree)
    {
    	int l = 0;
    	int r = 0;
    	
    	if(tree == NULL)
    	{
    		return 0;
    	}
    	{
    		l = height(tree->left);
    		r = height(tree->right);
    		if( l > r || l == r)
    		{
    			return (l + 1);
    		}
    		else
    		{
    			return (r + 1);
    		}
    	}
    }

    Can you point my mistake and help me to fix it please?
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  2. #2
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    There is no error in your code. The height of the tree is 5. When you insert numbers into a binary tree in order, they form a degenerate tree, equivalent to a linked list. This tree has empty left nodes. Congratulations, you have discovered the need for tree balancing.

  3. #3
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    thanks for your reply
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 09:11 AM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Inserting words into a binary search tree
    By lime in forum C Programming
    Replies: 9
    Last Post: 08-02-2003, 11:02 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21