How to find out the deepest node in BST?

Question

private int Depth(TreeNode node) { if (node == null) { return -1; } else { return 1 + Math.Max(Depth(node.LeftNode),Depth(node.RightNode)); } } 

I wrote a method to find the deepest node, but I'm not sure about this method.
Is this the right way to find the deepest node?

Answer 1

(Assuming you want to get the height of the tree, including the node specified as a parameter)

For an empty tree ( node == null ) you get a depth of -1. For a tree with 1 node you will get:

 1 + max(-1, -1) = 0 

etc., returning 0 should fix the problem, but the general idea is fine.

As for optimization ... if only you know about this tree, it is a binary tree, then this is the best that you can get without caching heights in nodes.

As for finding the nearest sheet, you can use the BFS algorithm to do this efficiently, because it will go and open the nodes horizontally, and then you can stop when you open the 1st sheet.

Pseudocode BFS:

  nodes.enqueue (tuple (node, 1)) // enqueue node with height == 1
 while (nodes.count> 0)
 {
   (node, h) = nodes.dequeue ()
   if (node.left == null && node.right == null) return h;  // If it first leaf we've found, return it height.

   // Enqueue our childs with their height
   if (node.left! = null)
     nodes.enqueue (node.left, h + 1);
   if (node.right! = null)
     nodes.enqueue (node.right, h + 1);
 }

Answer 2

The deepest node BST is called height.

Here you can see how to calculate the height of the BST.

In principle, you are right.