Write The Shortest Program to Calculate Height of a Binary Tree
Jelly, 3 bytes
ŒḊ’
A monadic Link accepting a list representing the tree: [root_value, left_tree, right_tree]
, where each of left_tree
and right_tree
are similar structures (empty if need be), which yields the height.
Try it online!
How?
Pretty trivial in Jelly:
ŒḊ’ - Link: list, as described above
ŒḊ - depth
’ - decremented (since leaves are `[value, [], []]`)
Python 2, 35 33 bytes
Thanks to Arnauld for noicing an oversight and saving 4.
f=lambda a:a>[]and-~max(map(f,a))
A recursive function accepting a list representing the tree: [root_value, left_tree, right_tree]
, where each of left_tree
and right_tree
are similar structures (empty if need be), which returns the height.
Try it online!
Note that []
will return False
, but in Python False==0
.
05AB1E, 11 7 5 bytes
Δ€`}N
-4 bytes thanks to @ExpiredData.
-2 bytes thanks to @Grimy.
Input format is similar as the Jelly answer: a list representing the tree: [root_value, left_tree, right_tree]
, where each of left_tree
and right_tree
are similar structures (optionally empty). I.e. [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]
represents the tree from the challenge description.
Try it online or verify a few more test cases.
Explanation:
Δ # Loop until the (implicit) input-list no longer changes:
€` # Flatten the list one level
}N # After the loop: push the 0-based index of the loop we just finished
# (which is output implicitly as result)
Note that although 05AB1E is 0-based, the changes-loop Δ
causes the output index to be correct, because it needs an additional iteration to check it no longer changes.