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 $"{Key}";
}
}
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) < 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) < 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("SEARCHEXAMPLE", 6)]
[TestCase("SEBAQRCHGEXAMPLE", 6)]
[TestCase("STUVWXYZEBAQRCHGEXAMPLE", 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.
