node values = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 11, 12, 13, 14, 15, 16, 17, 18, 19] ==== create tree (un-balanced) ======================== ---------- initial tree structure -------------------- ------------------------------ 19 (p=18) --------------------------- 18 (p=17) ------------------------ 17 (p=16) --------------------- 16 (p=15) ------------------ 15 (p=14) --------------- 14 (p=13) ------------ 13 (p=12) --------- 12 (p=11) ------ 11 (p=10) --- 10 (p=None) ------ 9 (p=10) --------- 8 (p=9) ------------ 7 (p=8) --------------- 6 (p=7) ------------------ 5 (p=6) --------------------- 4 (p=5) ------------------------ 3 (p=4) --------------------------- 2 (p=3) ------------------------------ 1 (p=2) Maximum height of tree is 10 Average height of tree is 5.40 ==== balanced tree ==================================== ---------- final tree structure ----------------------- ------------------ 19 (p=18) --------------- 18 (p=16) ------------------ 17 (p=18) ------------ 16 (p=14) --------------- 15 (p=16) --------- 14 (p=12) ------------ 13 (p=14) ------ 12 (p=10) --------- 11 (p=12) --- 10 (p=None) --------- 9 (p=8) ------ 8 (p=10) ------------ 7 (p=6) --------- 6 (p=8) --------------- 5 (p=4) ------------ 4 (p=6) ------------------ 3 (p=2) --------------- 2 (p=4) ------------------ 1 (p=2) Maximum height of tree is 6 Average height of tree is 3.80