Finding height in Binary Search Tree

by

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<T> aNode) {
    if (aNode == null) {
        return -1;
    }

    int lefth = findHeight(aNode.left);
    int righth = findHeight(aNode.right);

    if (lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}

More Related Contents:

  1. What is tail recursion?
  2. What is tail call optimization?
  3. Understanding recursion [closed]
  4. Is log(n!) = Θ(n·log(n))?
  5. How to find all combinations of coins when given some dollar value [closed]
  6. recursion versus iteration
  7. Breadth First Vs Depth First
  8. Design patterns for converting recursive algorithms to iterative ones
  9. Heap vs Binary Search Tree (BST)
  10. find all subsets that sum to a particular value
  11. Store the largest 5000 numbers from a stream of numbers
  12. How do you validate a binary search tree?
  13. SICP example: Counting change, cannot understand
  14. Quicksort: Iterative or Recursive
  15. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  16. Basic Recursion, Check Balanced Parenthesis
  17. In Order Successor in Binary Search Tree
  18. Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin
  19. Why is my recursive function so slow in R?
  20. Convert recursion to tail recursion
  21. Memory efficient power set algorithm
  22. Pseudocode – Largest to smallest integer [closed]
  23. RGB values of visible spectrum
  24. Division without using ‘/’
  25. Precise subpixel line drawing algorithm (rasterization algorithm)
  26. Algorithm to find next greater permutation of a given string
  27. How to partition an array of integers in a way that minimizes the maximum of the sum of each partition?
  28. How to rank a million images with a crowdsourced sort
  29. algorithm for index numbers of triangular matrix coefficients
  30. Search a sorted 2D matrix [duplicate]

Leave a Comment