ns was wondering if anybody could assist me rework this an approach to find the height of a binary search tree. Therefore far, my code looks favor this. However, the prize I"m obtaining is larger than the actual elevation by 1. Yet when I remove the +1 from mine return statements, it"s much less than the actual height by 1. I"m still trying to wrap my head approximately recursion through these BST. Any aid would be lot appreciated.

You are watching: How to find the height of a binary search tree

public int findHeight() if(this.isEmpty()) return 0; else TreeNode node = root; return findHeight(node); private int findHeight(TreeNode 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;
algorithm recursion binary-search-tree
re-publishing
boost this question
monitor
edited Jun 7 "20 in ~ 7:02

*

wdmssk
3311 gold badge22 silver- badges44 bronze badges
request Apr 8 "10 at 4:47
*

mikemike
2,96966 gold badges2828 silver badges3333 bronze badges
2
include a comment |

24 answer 24


energetic oldest Votes
140
The difficulty lies in her base case.

"The elevation of a tree is the size of the route 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 in ~ the end.

So if over there isn"t a node, friend return -1 i m sorry cancels the end the +1.

int findHeight(TreeNode aNode) if (aNode == null) return -1; int lefth = findHeight(aNode.left); int righth = findHeight(aNode.right); if (lefth > righth) return lefth + 1; rather return righth + 1;
share
enhance this answer
monitor
edited Aug 14 "16 in ~ 1:50

*

TheHamCo
1311 silver- badge33 bronze badges
answer Apr 8 "10 in ~ 5:26
*

CoreyCorey
3,00511 gold badge1616 silver- badges1414 bronze badges
8
| show 3 an ext comments
38
The elevation of a binary search tree is equal to variety of layers - 1.

See the diagram at http://en.wikipedia.org/wiki/Binary_tree

Your recursion is good, so just subtract one in ~ the source level.

Also note, you can clean up the duty a little by managing null nodes:

int findHeight(node) if (node == null) return 0; return 1 + max(findHeight(node.left), findHeight(node.right));
re-publishing
improve this answer
follow
reply Apr 8 "10 at 5:08

*

StephenStephen
44k77 gold badges5757 silver badges6767 bronze title
5
add a comment |
25
int getHeight(Node node) if (node == null) return -1; return 1 + Math.max(getHeight(node.left), getHeight(node.right));
re-superstructure
boost this price
follow
edited might 30 "16 in ~ 16:58
Jared Burrows
51.8k2222 yellow badges146146 silver badges182182 bronze title
answer Sep 25 "14 at 5:20
HarishHarish
25933 silver- badges22 bronze badges
add a comment |
11
In mine opinion, your password would benefit from being streamlined a bit. Fairly than attempting to finish the recursion once a child reminder is null, only finish it once the current tip is null. That renders the password a lot much easier to write. In pseudo-code, the looks something like this:

if (node = null) return 0;else left = height(node->left); right = height(node->right); return 1 + max(left, right);
re-superstructure
improve this prize
follow
edited Nov 5 "19 in ~ 6:58
soul
6966 bronze badges
reply Apr 8 "10 at 5:06
Jerry CoffinJerry Coffin
444k7474 gold badges582582 silver- badges10411041 bronze badges
6
| display 1 an ext comment
5
class Solution{ public revolution 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;
re-superstructure
enhance this prize
follow
edited Jul 13 "16 in ~ 13:20
Ami Hollander
2,17122 gold badges2828 silver- badges4343 bronze badges
reply Jul 13 "16 at 12:13
user17711user17711
5111 silver badge11 bronze argorial
include a comment |
5
For world like me who favor 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;
share
improve this answer
follow
answer Mar 26 "17 at 5:37
lingareddyklingareddyk
17533 silver badges1212 bronze title
include a comment |
4
Here"s a concise and hopefully correct method to refer it:

exclusive int findHeight(TreeNode aNode)If the present node is null, there"s no tree. If both children are, there"s a solitary layer, which method 0 height. This uses the meaning of elevation (mentioned by Stephen) together # of class - 1


re-publishing
boost this prize
follow
edited Apr 8 "10 at 5:24
reply Apr 8 "10 in ~ 4:51
Matthew FlaschenMatthew Flaschen
261k4747 gold badges494494 silver badges530530 bronze badges
0
include a comment |
4
This is untested, but fairly obviously correct:

private int findHeight(Treenode aNode) if (aNode.left == null && aNode.right == null) return 0; // was 1; apparently a node through no youngsters has a height of 0. rather if (aNode.left == null) return 1 + findHeight(aNode.right); else if (aNode.right == null) return 1 + findHeight(aNode.left); rather return 1 + max(findHeight(aNode.left), findHeight(aNode.right)); Often simplifying your code is easier than figuring the end why it"s turn off by one. This password is basic to understand: the four possible cases are clearly handled in one 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 appropriate trees (but not both!) are null, return the elevation of the non-null tree, to add 1 to account because that the included height the the existing node.If no tree is null, return the height of the taller subtree, again plus one for the existing node.
re-superstructure
boost this answer
monitor
edited Feb 8 "20 in ~ 14:48
Torakun
2366 bronze title
answer Apr 8 "10 in ~ 5:15
jemfinchjemfinch
2,8231717 silver- badges2424 bronze title
3
include a comment |
3
publicly void HeightRecursive() Console.WriteLine( HeightHelper(root) ); personal int HeightHelper(TreeNode node) if (node == null) return -1; else return 1 + Math.Max(HeightHelper(node.LeftNode),HeightHelper(node.RightNode)); C# code.Include this two techniques in her BST class. You need two method to calculate height of tree. HeightHelper calculate it, & HeightRecursive publish it in main().


re-superstructure
enhance this answer
follow
answered Dec 5 "11 at 11:50
DesireDesire
52344 yellow badges1212 silver badges2828 bronze title
add a comment |
2
The definition given above of the elevation is incorrect. That is the meaning of the depth.

"The depth the a node M in a tree is the length of the route 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 room at level d in the tree. The root is the just node at level 0, and also its depth is 0."

Citation: "A Practical introduction to Data Structures and Algorithm Analysis"Edition 3.2 (Java Version)Clifford A. ShafferDepartment of computer ScienceVirginia TechBlacksburg, VA 24061


re-publishing
boost this prize
monitor
answered may 9 "13 at 1:31
amyersamyers
2111 bronze badge
add a comment |
2
public int height() if(this.root== null) return 0; int leftDepth = nodeDepth(this.root.left, 1); int rightDepth = nodeDepth(this.root.right, 1); int elevation = 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;
re-superstructure
boost this answer
monitor
edited Sep 12 "17 in ~ 1:32
Pang
8,832144144 yellow badges8282 silver- badges115115 bronze badges
reply Dec 31 "16 in ~ 1:59
Saikrishna RaoSaikrishna Rao
48555 silver badges44 bronze title
add a comment |
2
//function to discover height that 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) amount = rheight + 1; return sum;
re-superstructure
enhance this answer
monitor
reply Oct 15 "17 in ~ 21:25
acekizzyacekizzy
6777 bronze badges
include a comment |
2
int height(Node* root) if(root==NULL) return -1; return max(height(root->left),height(root->right))+1;Take that maximum height from left and also right subtree and include 1 come it.This likewise handles the base case(height that Tree through 1 node is 0).

See more: Thing 1 And Thing 2 Characters, Thing One And Thing Two


re-publishing
boost this answer
follow
answered Aug 19 "18 at 5:02
Mahendra sutharMahendra suthar
36133 silver- badges1818 bronze title
include a comment |
2
I recognize that i’m late come the party. ~ looking right into wonderful answers noted here, I thought mine will include some value to this post. Although the posted answers space amazing and easy to understand however, all room calculating the elevation to the BST in straight time. Ns think this can be improved and also Height can be retrieved in constant time, hence writing this price – expect you will choose it.Let’s start with the Node class:

public class Node public Node(string key) key = key; elevation = 1; publicly int height get; set; public string vital get; set; public Node Left get; set; windy Node ideal get; set; public override string ToString() return $"Key"; BinarySearchTree class

So you can have guessed the cheat here… Im keeping node circumstances variable height to keep track of each node when added.Lets relocate to the BinarySearchTree class that permits us to add nodes into our BST:

public class BinarySearchTree{ windy Node RootNode get; private set; publicly void Put(string key) if (ContainsKey(key)) return; RootNode = Put(RootNode, key); private Node Put(Node node, wire key) { if (node == null) return brand-new Node(key); if (node.Key.CompareTo(key) as soon as we have included the key, values in the BST, we can just speak to Height property on the RootNode object that will certainly return united state the height of the RootNode tree in constant time.The trick is to store the height updated when a brand-new node is added into the tree.Hope this helps someone out there in the wild people of computer system science enthusiast!

Unit test:

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 procedure is motivated by the size of BST method found in the third chapter (page 399) that Algorithm (Fourth Edition) book.