data structures - Calculating the height of a binary tree -
i need theory on calculating height of binary tree, typically notation.
i have read following article:
calculating height of binary tree
and 1 of posts gives following notation:
height(node) = max(height(node.l), height(node.r)) + 1
let's assume have following binary tree:
10 / \ 5 30 / \ / \ 4 8 28 42
do therefore calculate max value on left node (8) , max node on right (42) , add 1? don't quite understand how notation works in order calculate height of tree.
i'll try explain how recursive algorithm works:
height(10) = max(height(5), height(30)) + 1 height(30) = max(height(28), height(42)) + 1 height(42) = 1 (no children) height(28) = 1 (no children) height(5) = max(height(4), height(8)) + 1 height(4) = 1 (no children) height(8) = 1 (no children)
so if want calculate height(10)
, have expand recursion down, , substitute results backwards.
height(5) = max(1, 1) + 1 height(30) = max(1, 1) + 1 height(10) = max(2, 2) + 1 height(10) = 3
Comments
Post a Comment