Finding height in Binary Search Tree

Question

I was wondering if anybody could help me rework this method to find the height of a binary search tree  So far  my code looks like this  However  the answer I m getting is larger than the actual height by 1  But when I remove the  1 from my return statements  it s less than the actual height by 1  I m still trying to wrap my head around recursion with these BST  Any help would be much appreciated   public int findHeight        if this isEmpty             return 0            else          TreeNode lt T gt  node   root          return findHeight node           private int findHeight TreeNode lt T gt  aNode       int heightLeft   0      int heightRight   0      if aNode left  null          heightLeft   findHeight aNode left       if aNode right  null          heightRight   findHeight aNode right       if heightLeft  gt  heightRight           return heightLeft 1            else          return heightRight 1

User · Answer

I guess this question could mean two different things...

Height is the number of nodes in the longest branch:-

int calcHeight(node* root){ if(root==NULL) return 0; int l=calcHeight(root->left); int r=calcHeight(root->right); if(l>r) return l+1; else return r+1; }
Height is the total number of nodes in the tree itself:

int calcSize(node* root){ if(root==NULL) return 0; return(calcSize(root->left)+1+calcSize(root->right)); }

User · Answer

int maxDepth BinaryTreeNode root        if root    null     root left    null  amp  amp  root right    null            return 0             return 1   Math max maxDepth root left   maxDepth root right

User · Answer

Set a tempHeight as a static variable initially 0     static void findHeight Node node  int count         if  node    null            return            if   node right    null   amp  amp   node left    null             if  tempHeight  lt  count                tempHeight   count                         findHeight node left    count       count--    reduce the height while traversing to a different branch     findHeight node right    count

User · Answer

int getHeight Node  root        if root    NULL  return -1     else             return max getHeight root- gt left   getHeight root- gt right     1

User · Answer

int getHeight Node node     if  node    null  return -1    return 1   Math max getHeight node left   getHeight node right

User · Answer

The definition given above of the height is incorrect  That is the definition of the depth     The depth of a node M in a tree is the length of the path from the root of the tree to M  The height of a tree is one more than the depth of the deepest node in the tree  All nodes of depth d are at level d in the tree  The root is the only node at level 0  and its depth is 0    Citation   A Practical Introduction to Data Structures and Algorithm Analysis  Edition 3 2  Java Version  Clifford A  Shaffer Department of Computer Science Virginia Tech Blacksburg  VA 24061

User · Answer

In my opinion  your code would benefit from being simplified a bit  Rather than attempting to end the recursion when a child pointer is null  only end it when the current pointer is null  That makes the code a lot simpler to write  In pseudo-code  it looks something like this   if  node   null      return 0  else     left   height node- gt left       right   height node- gt right       return 1   max left  right

User · Answer

public int getHeight Node node        if node    null          return 0       int left val   getHeight node left       int right val   getHeight node right       if left val  gt  right val          return left val 1      else         return right val 1

User · Answer

function to find height of BST  int height Node  root        if root    NULL           return -1             int sum 0      int rheight   height root- gt right       int lheight   height root- gt left        if lheight gt rheight           sum   lheight  1            if rheight  gt  lheight           sum   rheight   1             return sum

User · Answer

Here is a solution in C       private static int heightOfTree Node root                if  root    null                        return 0                     int left   1   heightOfTree root left           int right   1   heightOfTree root right            return Math Max left  right

User · Answer

For anyone else that reads this      HEIGHT is defined as the number of nodes in the longest path from the root node to a leaf node  Therefore  a tree with only a root node has a height of 1 and not 0   The LEVEL of a given node is the distance from the root plus 1  Therefore  The root is on level 1  its child nodes are on level 2 and so on    Information courtesy of Data Structures  Abstraction and Design Using Java  2nd Edition  by Elliot B  Koffman  amp  Paul A  T  Wolfgang  - Book used in Data Structures Course I am currently taking at Columbus State University

User · Answer

class Solution      public static int getHeight Node root            int height   -1           if  root    null                return height            else               height   1   Math max getHeight root left   getHeight root right                       return height

User · Answer

The height of a binary search tree is equal to number of layers - 1   See the diagram at http   en wikipedia org wiki Binary tree  Your recursion is good  so just subtract one at the root level   Also note  you can clean up the function a bit by handling null nodes    int findHeight node      if  node    null  return 0    return 1   max findHeight node left   findHeight node right

User · Answer

Height of Binary Tree public static int height Node root                   Base case  empty tree has height 0         if  root    null                return 0                        recursively for left and right subtree and consider maximum depth         return 1   Math max height root left   height root right

User · Answer

public void HeightRecursive                 Console WriteLine  HeightHelper root                 private int HeightHelper TreeNode node                if  node    null                        return -1                    else                       return 1   Math Max HeightHelper node LeftNode  HeightHelper node RightNode                                 C  code  Include these two methods in your BST class  you need two method to calculate height of tree  HeightHelper calculate it   amp  HeightRecursive print it in main

User · Answer

Here is a solution in Java a bit lengthy but works    public static int getHeight  Node root       int lheight   0  rheight   0      if root  null            return 0            else           if root left    null                lheight   1   getHeight root left               System out println  lheight          lheight                     if  root right    null                rheight   1  getHeight root right               System out println  rheight          rheight                     if root    null  amp  amp  root left    null  amp  amp  root right    null                lheight    1               rheight    1                       return Math max lheight  rheight

User · Answer

int height Node  root            if root  NULL  return -1          return max height root- gt left  height root- gt right   1      Take of maximum height from left and right subtree and add 1 to it This also handles the base case height of Tree with 1 node is 0

User · Answer

Here s a concise and hopefully correct way to express it     private int findHeight TreeNode lt T gt  aNode       if aNode    null     aNode left    null  amp  amp  aNode right    null         return 0      return Math max findHeight aNode left   findHeight aNode right     1        If the current node is null  there s no tree   If both children are  there s a single layer  which means 0 height   This uses the definition of height  mentioned by Stephen  as   of layers - 1

User · Answer

The problem lies in your base case     The height of a tree is the length of the path from the root to the deepest node in the tree  A  rooted  tree with only a node  the root  has a height of zero   - Wikipedia   If there is no node  you want to return -1 not 0   This is because you are adding 1 at the end   So if there isn t a node  you return -1 which cancels out the  1   int findHeight TreeNode lt T gt  aNode        if  aNode    null            return -1             int lefth   findHeight aNode left       int righth   findHeight aNode right        if  lefth  gt  righth            return lefth   1        else           return righth   1

User · Answer

public int height         if this root   null  return 0       int leftDepth   nodeDepth this root left  1       int rightDepth   nodeDepth this root right  1        int height   leftDepth  gt  rightDepth  leftDepth  rightDepth       return height      private int nodeDepth Node node  int startValue        int nodeDepth   0       if node left    null  amp  amp  node right    null  return startValue      else          startValue            if node left   null               nodeDepth   nodeDepth node left  startValue                      if node right   null               nodeDepth   nodeDepth node right  startValue                        return nodeDepth

User · Answer

enter image description here  According to  Introduction to Algorithms  by Thomas H  Cormen  Charles E  Leiserson  Ronald L  Rivest  and Clifford Stein  following is the definition of tree height      The height of a node in a   tree is the number of edges on the longest simple downward path from the node to   a leaf  and the height of a tree is the height of its root  The height of a tree is also   equal to the largest depth of any node in the tree    Following is my ruby solution  Most of the people forgot about height of empty tree or tree of single node in their implementation   def height node  current height    return current height if node nil      node left nil   amp  amp  node right nil     return  height node left  current height   1   height node right  current height   1   max if node left  amp  amp  node right   return height node left  current height   1  if node left   return height node right  current height   1  end

User · Answer

For people like me who like one line solutions   public int getHeight Node root        return Math max root left    null   getHeight root left    -1                       root right    null   getHeight root right    -1                         1

User · Answer

I know that I   m late to the party  After looking into wonderful answers provided here  I thought mine will add some value to this post  Although the posted answers are amazing and easy to understand however  all are calculating the height to the BST in linear time  I think this can be improved and Height can be retrieved in constant time  hence writing this answer     hope you will like it  Let   s start with the Node class  public class Node       public Node string key                Key   key          Height   1                 public int Height   get  set         public string Key   get  set        public Node Left   get  set        public Node Right   get  set         public override string ToString                 return   quot  Key  quot            BinarySearchTree class So you might have guessed the trick here    Im keeping node instance variable Height to keep track of each node when added  Lets move to the BinarySearchTree class that allows us to add nodes into our BST  public class BinarySearchTree       public Node RootNode   get  private set         public void Put string key                if  ContainsKey key                         return                     RootNode   Put RootNode  key              private Node Put Node node  string key                if  node    null  return new Node key            if  node Key CompareTo key   lt  0                        node Right   Put node Right  key                     else                       node Left   Put node Left  key                                        since each node has height property that is maintained through this Put method that creates the binary search tree             calculate the height of this node by getting the max height of its left or right subtree and adding 1 to it                  node Height   Math Max GetHeight node Left   GetHeight node Right     1          return node             private int GetHeight Node node                return node  Height    0             public Node Get Node node  string key                if  node    null  return null          if  node Key    key  return node           if  node Key CompareTo key   lt  0                           node Key   M  key   P which results in -1             return Get node Right  key                      return Get node Left  key              public bool ContainsKey string key                Node node   Get RootNode  key           return node    null           Once we have added the key  values in the BST  we can just call Height property on the RootNode object that will return us the Height of the RootNode tree in constant time  The trick is to keep the height updated when a new node is added into the tree  Hope this helps someone out there in the wild world of computer science enthusiast  Unit test   TestCase  quot SEARCHEXAMPLE quot   6    TestCase  quot SEBAQRCHGEXAMPLE quot   6    TestCase  quot STUVWXYZEBAQRCHGEXAMPLE quot   8   public void HeightTest string data  int expectedHeight           Arrange      var runner   GetRootNode data                 Assert      Assert AreEqual expectedHeight  runner RootNode Height      private BinarySearchTree GetRootNode string data        var runner   new BinarySearchTree        foreach  char nextKey in data                runner Put nextKey ToString                return runner     Note  This idea of keeping the Height of tree maintained in every Put operation is inspired by the Size of BST method found in the 3rd chapter  page 399  of Algorithm  Fourth Edition  book

User · Answer

This is untested  but fairly obviously correct   private int findHeight Treenode lt T gt  aNode      if  aNode left    null  amp  amp  aNode right    null        return 0     was 1  apparently a node with no children has a height of 0      else if  aNode left    null        return 1   findHeight aNode right       else if  aNode right    null        return 1   findHeight aNode left       else       return 1   max findHeight aNode left   findHeight aNode right            Often simplifying your code is easier than figuring out why it s off by one   This code is easy to understand  the four possible cases are clearly handled in an obviously correct manner    If both the left and right trees are null  return 0  since a single node by definition has a height of 0   was 1  If either the left or right trees  but not both   are null  return the height of the non-null tree  plus 1 to account for the added height of the current node  If neither tree is null  return the height of the taller subtree  again plus one for the current node

[algorithm] Finding height in Binary Search Tree

Examples related to algorithm

Examples related to recursion

Examples related to binary-search-tree