EasyPython ProgrammingHigh School (11–12)High School (9–10)UndergraduateGeneralPython Going Further › Data StructuresConceptualA-LevelIB
Insert the values 50, 30, 70, 20, 40, 60, 80, 30 into an empty binary search tree, in that order…
Contributed by StemPy LabTry it on paper first. A hint, the key idea and the worked solution are here when you need them.
Insert the values 50, 30, 70, 20, 40, 60, 80, 30 into an empty binary search tree, in that order. Draw the tree in words (who is the left and right child of whom), and write the in-order walk.
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. Start at the root and go left for smaller, right for bigger.
- 50 is the root.
- 30 is less than 50: left child of 50.
- 70 is more than 50: right child of 50.
- 20 is less than 50, less than 30: left child of 30.
- 40 is less than 50, more than 30: right child of 30.
- 60 is more than 50, less than 70: left child of 70.
- 80 is more than 50, more than 70: right child of 70.
- 30 again: it is already there, so it is ignored.
The tree is full and balanced: the root 50, then 30 and 70, then 20, 40, 60 and 80, which are the leaves. The height is 3.
The in-order walk (left, node, right) gives the sorted values: 20, 30, 40, 50, 60, 70, 80.
Answer: The tree above, and 20, 30, 40, 50, 60, 70, 80.
Discussion (0)
Log in to join the discussion.
Loading…