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
request Apr 8 "10 in ~ 4:47 mikemike
2

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
reply Apr 8 "10 at 5:26 CoreyCorey
8
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
5
25
int getHeight(Node node) if (node == null) return -1; return 1 + Math.max(getHeight(node.left), getHeight(node.right));
re-publishing
monitor
edited might 30 "16 at 16:58
Jared Burrows
answered Sep 25 "14 in ~ 5:20
HarishHarish
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
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
monitor
edited Jul 13 "16 in ~ 13:20
Ami Hollander
reply Jul 13 "16 in ~ 12:13
user17711user17711
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
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
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
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
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
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
answered Dec 31 "16 in ~ 1:59
Saikrishna RaoSaikrishna Rao
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
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