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
request Apr 8 "10 at 4:47 mikemike
2
include a comment |

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
monitor
edited Aug 14 "16 in ~ 1:50 TheHamCo
answer Apr 8 "10 in ~ 5:26 CoreyCorey
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
follow
reply Apr 8 "10 at 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-superstructure
boost this price
follow
edited might 30 "16 in ~ 16:58
Jared Burrows
answer Sep 25 "14 at 5:20
HarishHarish
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
reply Apr 8 "10 at 5:06
Jerry CoffinJerry Coffin
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
reply Jul 13 "16 at 12:13
user17711user17711
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
follow
answer Mar 26 "17 at 5:37
lingareddyklingareddyk
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
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
monitor
edited Feb 8 "20 in ~ 14:48
Torakun
2366 bronze title
answer Apr 8 "10 in ~ 5:15
jemfinchjemfinch
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
follow
answered Dec 5 "11 at 11:50
DesireDesire
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
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
monitor
edited Sep 12 "17 in ~ 1:32
Pang
reply Dec 31 "16 in ~ 1:59
Saikrishna RaoSaikrishna Rao
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
monitor
reply Oct 15 "17 in ~ 21:25
acekizzyacekizzy
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
follow
answered Aug 19 "18 at 5:02
Mahendra sutharMahendra suthar