Java: Minimum Depth of Binary search Tree Recursive

Question

I am writing the code to calculate minimum depth of binary tree
My solution works well for tree BST if the inputs are 6,4,9,3,5,7,12,2,8
because minimum depth is coming as 3 which is correct.
But when the tree is 3,2 , minimum depth is coming as 1 instead of 2.
My code snippet is:

int minimumHeightRec(TreeNode root)
        {
            if(root == null) return 0;
            int left = minimumHeightRec(root.left);
            int right = minimumHeightRec(root.right);
            if(left > right) return right + 1;
            else return left + 1;
        }

When you say "when the tree is 3,2" do you mean the input? In that case, the root node will be "3" and the left node will be "2", while the right node will be null; in which case, returning 1 as minimum tree depth is correct. — Zaphod Beeblebrox
– Zaphod Beeblebrox, Commented Oct 17, 2015 at 20:01

Ling Zhong · Accepted Answer · 2015-10-18 15:10:36Z

1

Your implementation is correct. The expected minHeight should be 1 instead of 2. Consider your example of [3, 2] the BST may have the following form:

  3
 /
2

looking into left of root has height of 2: (3) -> (2)

looking into right of root has height of 1: (3)

You're looking for the minHeight of the BST, so taking the right branch of height 1 is the correct choice.

Note that you may have a different tree form where 2 is the root, but the logic and result will be the same.

edited Oct 18, 2015 at 15:10

answered Oct 17, 2015 at 19:51

Ling Zhong

1,8141 gold badge15 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

ojas Over a year ago

But i solved this question in Leetcode and its showing wrong. Refer leetcode.com/problems/minimum-depth-of-binary-tree

Ling Zhong Over a year ago

I see where the difference is, in the link you provided they define depth down to a leaf nodes which must have zero child. Which means in the case of [3, 2] root does not count, since root (3) has a child (2). Hope this helps.

Zaphod Beeblebrox Over a year ago

I don't see how the tree you've written, Ling Zhong, has a right branch. There's only one root (3) and one left branch with a leaf (2). There's no right branch.

Ling Zhong Over a year ago

@ZaphodBeeblebrox I should phrase it better, it's more of looking into right of root. Please see edit.

user3818296 · Accepted Answer · 2015-10-17 19:53:00Z

0

The else is useless because there is a return in the if.
Some more code (TreeNode class and main) would be usefull.

answered Oct 17, 2015 at 19:53

user3818296

1 Comment

Jiri Tousek Over a year ago

The else actually improves readability since it makes it explicit under which condition it will be reached.

Collectives™ on Stack Overflow

Java: Minimum Depth of Binary search Tree Recursive

2 Answers 2

4 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related