1
$\begingroup$

Given the depth of the tree, I need to calculate the longest possible path in the full binary tree (also known as the diameter).

When attempting this problem, I experimented with what the depth has to do with the path length. However, the solutions I came up with depended on going through the root, while the longest path could obviously exist outside of the root.

What's an equation I can use to find the diameter of the full binary tree using the depth?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ If "full binary tree" you mean "fully occupied" so it is balanced you can use height. Otherwise traversing the tree will be needed. $\endgroup$
    – Evil
    Commented Dec 11, 2015 at 7:57

1 Answer 1

Reset to default
5
$\begingroup$

If it is a full binary tree, that is defined as:

Full binary tree is a tree in which every node other than the leaves has two children.

Then you know the depth $D$ will be half of the total possible diameter. This is because we can take a maximum possible path of length $D$ from root to any leaf in the subtree rooted at the left-child of the root, and we can also take a maximum possible path of length $D$ from root to any leaf in the subtree rooted at the right-child of the root. Thus, adding these up would be a path of length $2D$.

Thus, we get that the maximum possible diameter would be equal to twice the depth (i.e. $\mathrm{diameter} = 2\cdot \mathrm{depth}$).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Why would the depth of the left subtree be the same as the depth of the right subtree? See the example full binary tree at wikipedia . $\endgroup$
    – Hendrik Jan
    Commented Apr 10, 2019 at 19:33
  • 1
    $\begingroup$ @HendrikJan that is a good point. It is not necessarily the case. However $2D$ would still be the longest possible path, so I think (?) it still answers the question unless OP would clarify what they mean by full. $\endgroup$
    – ryan
    Commented Apr 10, 2019 at 20:42
  • $\begingroup$ @HendrikJan since you asked for a "longest possible path" it seems as though you want some upper bound. If you had wanted "the longest path" in a given tree, it would make a different question $\endgroup$
    – lox
    Commented Apr 10, 2019 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.