Finding the maximum depth of a binary tree

Question

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int maxDepth(TreeNode root) {
        TreeNode focusNode = root;
        TreeNode focusNode2 = root;
        int count = 0;
        int count1 = 0;
        boolean a = true;
        while (a) {
           if (focusNode != null) {
               count++;
               focusNode = focusNode.left;
           }
           if (focusNode2 != null) {
               count++;
               focusNode2 = focusNode2.right;
           } else {
               a = false;
           }
        }
        return Math.max(count,count1);
    }
}

I am confused why this code I wrote cannot give expected output. And I am also confused with the definition of maximum depth. Is finding maximum depth just considering all the nodes that line up on the left or line up on the right?

Can you draw a tree where that's not true?

Oliver Charlesworth
– Oliver Charlesworth

2017-03-31 23:34:53 +00:00
Commented Mar 31, 2017 at 23:34 — Oliver Charlesworth
– Oliver Charlesworth, Commented Mar 31, 2017 at 23:34

J.Chim · Accepted Answer · 2017-04-01 00:00:06Z

I'm not sure are you talking about the height of tree or depth of a node.
Here is the definition of height and depth.

Height of node – The height of a node is the number of edges on the longest downward path between that node and a leaf.

Depth –The depth of a node is the number of edges from the node to the tree's root node.

For example:
the depth for node R is 0 and height is 3
the depth for node G is 3 and height is 0

Let assume you are finding the height of tree.
why your program can't get the outcome of what you desires?
It's because your code didn't traverse all nodes inside the tree

Let use the tree in diagram as example:
In your loop it will first let focusNode, focusNode2 = node R

focusNode R > A > C
focusNode2 R > B > F > Terminate

All sub nodes inside middle of tree didn't count, if your tree is not a perfect binary tree then you will get the wrong answer.

Suggest that you can read some algorithm on how to traverse a tree like Pre-order Travesal
https://en.wikipedia.org/wiki/Tree_traversal

Bohemian · Accepted Answer · 2017-04-01 01:22:56Z

1

You're not traversing the whole tree. You're running down the far left and far right paths only.

Typically, recursion is your friend with binary trees, because every node can be treated simply and in isolation.

Define a depth() method for the node class, that makes use of these facts:

the depth of a null child is zero
the depth of a non-null child is found by calling its depth() method (ie recursively)
the depth of this node is the max of its children's depths, plus 1 (so it counts itself)

Implement that and call depth() on the root node to find the max depth of the tree. The recursive nature of the corresponding implementation will traverse the whole tree.

answered Apr 1, 2017 at 1:22

Bohemian♦

427k103 gold badges603 silver badges750 bronze badges

Collectives™ on Stack Overflow

Finding the maximum depth of a binary tree

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related