i was wondering if anybody could assist me rework this technique to discover the height of a binary find tree. So far, my password looks like this. However, the answer I"m gaining is larger than the actual height by 1. However when I eliminate the +1 from mine return statements, it"s much less than the actual height by 1. I"m quiet trying come wrap mine head roughly recursion v these BST. Any help 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-superstructure
improve this inquiry
follow
edited Jun 7 "20 in ~ 7:02

*

wdmssk
3311 yellow badge22 silver badges44 bronze badges
request Apr 8 "10 in ~ 4:47
*

mikemike
2,96966 gold badges2828 silver- badges3333 bronze title
2
add a comment |

24 answers 24


active oldest Votes
140
The problem lies in her base case.

"The height of a tree is the size of the course from the root to the deepest node in the tree. A (rooted) tree with only a node (the root) has a elevation of zero." - Wikipedia

If over there is no node, you desire to return -1 not 0. This is since you are adding 1 at the end.

So if over there isn"t a node, friend return -1 which cancels out 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; else return righth + 1;
re-publishing
improve this price
monitor
edited Aug 14 "16 at 1:50

*

TheHamCo
1311 silver badge33 bronze title
reply Apr 8 "10 at 5:26
*

CoreyCorey
3,00511 yellow badge1616 silver- badges1414 bronze title
8
| display 3 more comments
38
The height of a binary find tree is same to number of layers - 1.

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

Your recursion is good, so just subtract one at the root level.

Also note, you deserve to clean up the duty a little bit by managing null nodes:

int findHeight(node) if (node == null) return 0; return 1 + max(findHeight(node.left), findHeight(node.right));
re-publishing
enhance this prize
monitor
answered Apr 8 "10 in ~ 5:08

*

StephenStephen
44.1k77 yellow 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-publishing
improve this answer
monitor
edited might 30 "16 at 16:58
Jared Burrows
51.9k2222 gold badges147147 silver- badges183183 bronze badges
answered Sep 25 "14 in ~ 5:20
HarishHarish
25933 silver badges22 bronze title
add a comment |
11
In my opinion, your password would advantage from being streamlined a bit. Quite than attempting to finish the recursion once a child pointer is null, only end it as soon as the current guideline is null. That provides the code a lot much easier to write. In pseudo-code, the looks something favor this:

if (node = null) return 0;else left = height(node->left); ideal = height(node->right); return 1 + max(left, right);
re-publishing
enhance this price
follow
edited Nov 5 "19 at 6:58
heart
6966 bronze title
answer Apr 8 "10 in ~ 5:06
Jerry CoffinJerry Coffin
445k7474 gold badges582582 silver- badges10411041 bronze title
6
| show 1 more comment
5
class Solution{ public revolution int getHeight(Node root) int elevation = -1; if (root == null) return height; rather elevation = 1 + Math.max(getHeight(root.left), getHeight(root.right)); return height;
re-publishing
improve this answer
monitor
edited Jul 13 "16 in ~ 13:20
Ami Hollander
2,17122 yellow badges2828 silver- badges4343 bronze title
reply Jul 13 "16 in ~ 12:13
user17711user17711
5111 silver badge11 bronze badge
add a comment |
5
For human being like me who favor one heat solutions:

public int getHeight(Node root) return Math.max(root.left != null ? getHeight(root.left) : -1, root.right != null ? getHeight(root.right) : -1) + 1;
re-superstructure
enhance this price
follow
answer Mar 26 "17 in ~ 5:37
lingareddyklingareddyk
17533 silver badges1212 bronze title
add a comment |
4
Here"s a concise and also hopefully correct method to to express it:

personal int findHeight(TreeNode aNode) (aNode.left == null && aNode.right == null)) return 0; return Math.max(findHeight(aNode.left), findHeight(aNode.right)) + 1; If the present node is null, there"s no tree. If both kids are, there"s a solitary layer, which way 0 height. This uses the definition of height (mentioned by Stephen) together # of layers - 1


re-superstructure
improve this prize
follow
edited Apr 8 "10 in ~ 5:24
reply Apr 8 "10 in ~ 4:51
Matthew FlaschenMatthew Flaschen
262k4747 gold badges495495 silver- badges530530 bronze badges
0
include a comment |
4
This is untested, but reasonably obviously correct:

private int findHeight(Treenode aNode) if (aNode.left == null && aNode.right == null) return 0; // was 1; apparently a node with no youngsters has a elevation of 0. else 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 much easier than figuring the end why it"s turn off by one. This password is basic to understand: the four feasible cases are clearly handled in an obviously correct manner:

If both the left and also right trees are null, return 0, since a solitary node by definition has a height of 0. (was 1)If either the left or ideal trees (but no both!) space null, return the elevation of the non-null tree, add to 1 come account for the added height of the current node.If no tree is null, return the height of the higher subtree, again plus one because that the current node.
re-superstructure
improve this price
follow
edited Feb 8 "20 at 14:48
Torakun
2366 bronze title
answered Apr 8 "10 in ~ 5:15
jemfinchjemfinch
2,8231717 silver badges2424 bronze title
3
include a comment |
3
public void HeightRecursive() Console.WriteLine( HeightHelper(root) ); exclusive int HeightHelper(TreeNode node) if (node == null) return -1; rather return 1 + Math.Max(HeightHelper(node.LeftNode),HeightHelper(node.RightNode)); C# code.Include this two techniques in your BST class. You need two method to calculate height of tree. HeightHelper calculate it, & HeightRecursive publish it in main().


re-superstructure
improve this prize
monitor
answer Dec 5 "11 in ~ 11:50
DesireDesire
52344 gold badges1212 silver badges2828 bronze title
add a comment |
2
The an interpretation given over of the height is incorrect. That is the an interpretation of the depth.

"The depth the a node M in a tree is the length of the course from the source of the tree come M. The elevation of a tree is one much more than the depth of the deepest node in the tree. Every nodes the depth d are at level d in the tree. The source is the only node in ~ level 0, and also its depth is 0."

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


re-publishing
boost this answer
follow
answered may 9 "13 in ~ 1:31
amyersamyers
2111 bronze argorial
include 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 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;
re-publishing
improve this prize
monitor
edited Sep 12 "17 in ~ 1:32
Pang
8,841144144 gold badges8282 silver badges116116 bronze badges
answered Dec 31 "16 in ~ 1:59
Saikrishna RaoSaikrishna Rao
48555 silver- badges44 bronze title
include a comment |
2
//function to find 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-publishing
enhance this price
follow
reply Oct 15 "17 in ~ 21:25
acekizzyacekizzy
6777 bronze title
add 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 add 1 come it.This additionally handles the base case(height of Tree v 1 node is 0).

See more: Which Technology Would Best Help The United States Wean Itself From Foreign Oil


re-publishing
enhance this prize
monitor
answer Aug 19 "18 at 5:02
Mahendra sutharMahendra suthar
37133 silver- badges1818 bronze title
add a comment |
2
I recognize that ns late come the party. After looking into wonderful answers provided here, I assumed mine will add some value to this post. Back the post answers space amazing and also easy to understand however, all room calculating the elevation to the BST in linear time. Ns think this deserve to be improved and Height deserve to be recall in constant time, for this reason writing this prize – hope you will favor it.Let’s start with the Node class:

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

So you might have guessed the trick here… Im keeping node circumstances variable elevation to store track of every node once added.Lets move to the BinarySearchTree course that permits us to include nodes into our BST:

public class BinarySearchTree{ windy Node RootNode get; private set; windy 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) once we have included the key, values in the BST, we have the right to just speak to Height home on the RootNode object that will certainly return united state the elevation of the RootNode tree in constant time.The trick is to keep the height updated as soon as a brand-new node is included into the tree.Hope this helps someone the end there in the wild human being of computer system science enthusiast!

Unit test:

public void HeightTest(string data, int expectedHeight) // Arrange. Var jogger = 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 maintaining the elevation of tree preserved in every Put operation is inspired by the size of BST technique found in the 3rd chapter (page 399) the Algorithm (Fourth Edition) book.