# Find the longest possible path in full binary tree

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?

• If "full binary tree" you mean "fully occupied" so it is balanced you can use height. Otherwise traversing the tree will be needed.
– Evil
Dec 11, 2015 at 7:57

## 1 Answer

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}$$).

• 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 . Apr 10, 2019 at 19:33
• @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.
– ryan
Apr 10, 2019 at 20:42
• @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
– lox
Apr 10, 2019 at 21:02