MediumPython ProgrammingHigh School (11–12)High School (9–10)UndergraduateGeneralPython Going Further › Data StructuresConceptualPython-CodedA-LevelIB
What is the height of the tree made by inserting 5, 3, 8, 1, 4, 7, 9 in that order, and of the one…
Contributed by StemPy LabTry it on paper first. A hint, the key idea and the worked solution are here when you need them.
What is the height of the tree made by inserting 5, 3, 8, 1, 4, 7, 9 in that order, and of the one made by inserting 1, 3, 4, 5, 7, 8, 9? Check with a program.
The worked solution
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, compare your working with the solution.
Plan. The first order gives a balanced tree: 5 is the root, 3 and 8 are its children, and 1, 4, 7, 9 are the leaves. The height is 3.
The second order is sorted. Each value is bigger than all before it, so each goes to the right of the last: a chain of 7 nodes. The height is 7.
Answer: 3 and 7.
Discussion (0)
Log in to join the discussion.
Loading…