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<T> node = root;
return findHeight(node);
}
}
private int findHeight(TreeNode<T> 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 > heightRight){
return heightLeft+1;
}
else{
return heightRight+1;
}
}
This question is related to
algorithm
recursion
binary-search-tree
Set a tempHeight as a static variable(initially 0).
static void findHeight(Node node, int count) {
if (node == null) {
return;
}
if ((node.right == null) && (node.left == null)) {
if (tempHeight < count) {
tempHeight = count;
}
}
findHeight(node.left, ++count);
count--; //reduce the height while traversing to a different branch
findHeight(node.right, ++count);
}
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));
}
This is untested, but fairly obviously correct:
private int findHeight(Treenode<T> aNode) {
if (aNode.left == null && 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:
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;
}
//function to find height of BST
int height(Node* root) {
if(root == NULL){
return -1;
}
int sum=0;
int rheight = height(root->right);
int lheight = height(root->left);
if(lheight>rheight){
sum = lheight +1;
}
if(rheight > lheight){
sum = rheight + 1;
}
return sum;
}
Here's a concise and hopefully correct way to express it:
private int findHeight(TreeNode<T> aNode){
if(aNode == null || (aNode.left == null && 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
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));
}
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));
}
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
int getHeight(Node node) {
if (node == null) return -1;
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}
int height(Node* root) {
if(root==NULL) return -1;
return max(height(root->left),height(root->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).
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 > right_val)
return left_val+1;
else
return right_val+1;
}
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 > rightDepth? leftDepth: rightDepth;
return height;
}
private int nodeDepth(Node node, int startValue){
int nodeDepth = 0;
if(node.left == null && 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;
}
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);
}
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->left);
right = height(node->right);
return 1 + max(left, right);
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? && node.right.nil?)
return [height(node.left, current_height + 1), height(node.right, current_height + 1)].max if node.left && node.right
return height(node.left, current_height + 1) if node.left
return height(node.right, current_height + 1)
end
int getHeight(Node* root)
{
if(root == NULL) return -1;
else return max(getHeight(root->left), getHeight(root->right)) + 1;
}
int maxDepth(BinaryTreeNode root) {
if(root == null || (root.left == null && root.right == null)) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
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 && root.left == null && root.right == null) {
lheight += 1;
rheight += 1;
}
}
return Math.max(lheight, rheight);
}
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.
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, & HeightRecursive print it in main().
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 & Paul A. T. Wolfgang) - Book used in Data Structures Course I am currently taking at Columbus State University.
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;
}
Source: Stackoverflow.com