Project P052
Binary search tree explorer
A binary search tree of whole numbers: insert keys, delete them - a leaf, a node with one child, or one with two, replaced by its successor - and search with the path shown. Walk it in order, pre-order and post-order, see its size, height, smallest and largest key, and see it drawn on its side.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-10
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
A binary search tree of whole numbers from -999 to 999, up to 40 keys. Insert keys, delete them, and search for one to see the path taken. Walk the tree in order, pre-order and post-order, see its size, height, smallest and largest key, and see it drawn.
main.eml- the menu, reading keys, and the messages for each operationtree.eml- the tree: inserting, searching, deleting, the three walks, the height and the drawing
How each part works:
- The tree is kept as in the corpus case
binary-search-tree: three parallel lists - the keys, each node's left child and its right child, -1 for none - plus the root, so every change is one assignment to one list position. Smaller keys go left and larger keys right; a key is in the tree at most once. - Deleting a leaf cuts it off. Deleting a node with one child lets the child take its place. Deleting a node with two children copies in the key of its successor - the smallest key in its right subtree, found by going right once and then left as far as possible - and cuts out the successor, which has no left child. The order of the keys never breaks.
- In order visits the left subtree, the node and the right subtree, which gives the keys sorted. Pre-order visits the node first: inserting the keys in that order builds the same tree again. Post-order visits the node last: an order in which every node can go after its children.
- The height counts levels: an empty tree has height 0 and a lone root 1. The drawing turns the tree on its side - the right subtree above its node and the left below, four spaces for each level down.
What is checked: menu choices 1 to 8; keys as whole numbers from -999 to 999, separated by spaces or commas, and a line with anything else inserts nothing; keys already in the tree are named and left; at most 40 keys. An empty answer cancels.
Sessions: sessions/basic.in loads the sample, the corpus case's keys 50 30 70 20 40 60 80 35, and walks it. - Searches: 35 is found in 4 steps, and 65 falls off the right of 60. - Deletes, one of each kind: 20, a leaf; 40, whose one child 35 moves up; and the root 50, whose two children make its successor 60 the new root. - Inserts: 45, 10, 90 and -5, typed with a comma and spaces, then a walk.
sessions/bad-input.in gives: - menu choices 0 and x; - walks, a drawing, a search and a delete on the empty tree; - the key lines "1 2 x", 1000 and -1000, each inserting nothing, and an empty one; - 5 5 3, where the second 5 is already there; - the keys abc and --5, with a delete and a search, both cancelled; - 1 to 8 inserted in order: the tree becomes a single right-leaning chain of height 8, and every walk but post-order lists the keys sorted; - 1 to 41 inserted middle first. The first 40 build a tree of height 6, the lowest any 40 keys can have, and the 41st is turned away at the limit.
Built on the verified corpus case binary-search-tree (a tree built by insertion in parallel lists, read back by a recursive in-order walk).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Binary search tree ==
Smaller keys go left, larger keys right. The tree is drawn on its side: right is up.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 0
Pick a number from 1 to 8.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> x
Pick a number from 1 to 8.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 4
The tree is empty.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 5
The tree is empty.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 3
key to search for> 7
The tree is empty.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 2
key to delete> 7
7 is not in the tree.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 1
keys to insert (-999 to 999)> 1 2 x
Not a key from -999 to 999: x. Nothing was inserted.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 1
keys to insert (-999 to 999)> 1000
Not a key from -999 to 999: 1000. Nothing was inserted.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 1
keys to insert (-999 to 999)> -1000
Not a key from -999 to 999: -1000. Nothing was inserted.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 1
keys to insert (-999 to 999)>
Cancelled.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 1
keys to insert (-999 to 999)> 5 5 3
Inserted 5 3.
Already in the tree: 5.
5
3
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 2
key to delete> abc
Type one whole number from -999 to 999.
key to delete>
Cancelled.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 3
key to search for> --5
Type one whole number from -999 to 999.
key to search for>
Cancelled.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 7
The tree is empty now.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 1
keys to insert (-999 to 999)> 1 2 3 4 5 6 7 8
Inserted 1 2 3 4 5 6 7 8.
8
7
6
5
4
3
2
1
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 4
In order: 1 2 3 4 5 6 7 8
Pre-order: 1 2 3 4 5 6 7 8
Post-order: 8 7 6 5 4 3 2 1
8 keys, height 8, smallest 1, largest 8.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 7
The tree is empty now.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 1
keys to insert (-999 to 999)> 21 10 31 5 15 26 36 2 7 12 18 23 28 33 39 1 3 6 8 11 13 16 19 22 24 27 29 32 34 37 40 4 9 14 17 20 25 30 35 38 41
Inserted 21 10 31 5 15 26 36 2 7 12 18 23 28 33 39 1 3 6 8 11 13 16 19 22 24 27 29 32 34 37 40 4 9 14 17 20 25 30 35 38.
The tree holds 40 keys, the most it takes; the last key typed, 41, was not inserted.
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 4
In order: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
Pre-order: 21 10 5 2 1 3 4 7 6 8 9 15 12 11 13 14 18 16 17 19 20 31 26 23 22 24 25 28 27 29 30 36 33 32 34 35 39 37 38 40
Post-order: 1 4 3 2 6 9 8 7 5 11 14 13 12 17 16 20 19 18 15 10 22 25 24 23 27 30 29 28 26 32 35 34 33 38 37 40 39 36 31 21
40 keys, height 6, smallest 1, largest 40.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 7
The tree is empty now.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 5
The tree is empty.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 8
Bye.
What was typed (35 lines)
0
x
4
5
3
7
2
7
1
1 2 x
1
1000
1
-1000
1
1
5 5 3
2
abc
3
--5
7
1
1 2 3 4 5 6 7 8
4
7
1
21 10 31 5 15 26 36 2 7 12 18 23 28 33 39 1 3 6 8 11 13 16 19 22 24 27 29 32 34 37 40 4 9 14 17 20 25 30 35 38 41
4
7
5
8
basic
interpreter: byte-equal== Binary search tree ==
Smaller keys go left, larger keys right. The tree is drawn on its side: right is up.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 6
The sample: 50 30 70 20 40 60 80 35, inserted in that order.
80
70
60
50
40
35
30
20
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 4
In order: 20 30 35 40 50 60 70 80
Pre-order: 50 30 20 40 35 70 60 80
Post-order: 20 35 40 30 60 80 70 50
8 keys, height 4, smallest 20, largest 80.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 3
key to search for> 35
Found 35 after 4 steps: 50 -> 30 -> 40 -> 35.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 3
key to search for> 65
65 is not in the tree: 50 -> 70 -> 60, and 60 has no child on the right, where it would go.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 2
key to delete> 20
Deleted 20, a leaf.
80
70
60
50
40
35
30
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 2
key to delete> 40
Deleted 40; its one child took its place.
80
70
60
50
35
30
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 2
key to delete> 50
Deleted 50. It had two children, so 60 - the smallest key on its right - moved up into its place.
80
70
60
35
30
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 1
keys to insert (-999 to 999)> 45, 10 90 -5
Inserted 45 10 90 -5.
90
80
70
60
45
35
30
10
-5
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 4
In order: -5 10 30 35 45 60 70 80 90
Pre-order: 60 30 10 -5 35 45 70 80 90
Post-order: -5 10 45 35 30 90 80 70 60
9 keys, height 4, smallest -5, largest 90.
1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit
choice> 8
Bye.
What was typed (16 lines)
6
4
3
35
3
65
2
20
2
40
2
50
1
45, 10 90 -5
4
8
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P052 binary search tree explorer: insert and delete keys, search with the
# path taken, walk the tree in order, pre-order and post-order, and see it
# drawn - with its size, height, smallest and largest key.
import tree
def trim(s):
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def words(s):
[] => out
"" => word
for c in s + " ":
if c == " " or c == ",":
if word != "":
out + [word] => out
"" => word
else:
word + c => word
return out
def key_of(s):
# A whole number from -999 to 999, as [ok, value].
s => digits
1 => sign
if len(s) > 1 and s[0] == "-":
s[1:len(s)] => digits
-1 => sign
if digits == "" or len(digits) > 3:
return [False, 0]
0 => n
for c in digits:
if not (c >= "0" and c <= "9"):
return [False, 0]
n * 10 + int(c) => n
return [True, sign * n]
def joined(xs, sep):
"" => s
for x in xs:
if s != "":
s + sep => s
s + str(x) => s
return s
def keys(t):
return tree.in_order(t, t[3], [])
def draw(t):
if t[3] == -1:
"The tree is empty." ^0
return
for line in tree.sideways(t, t[3], 0, []):
line ^0
def insert_keys(t):
words(trim(input("keys to insert (-999 to 999)> "))) => ws
if len(ws) == 0:
"Cancelled." ^0
return
[] => values
for w in ws:
key_of(w) => k
if not k[0]:
("Not a key from -999 to 999: " + w + ". Nothing was inserted.") ^0
return
values + [k[1]] => values
[] => added
[] => there
0 => k
while k < len(values) and len(keys(t)) < 40:
if tree.insert(t, values[k]):
added + [values[k]] => added
else:
there + [values[k]] => there
k + 1 => k
if len(added) > 0:
("Inserted " + joined(added, " ") + ".") ^0
if len(there) > 0:
("Already in the tree: " + joined(there, " ") + ".") ^0
len(values) - k => rest
if rest == 1:
("The tree holds 40 keys, the most it takes; the last key typed, " + str(values[k]) + ", was not inserted.") ^0
elif rest > 1:
("The tree holds 40 keys, the most it takes; the last " + str(rest) + " keys typed, from " + str(values[k]) + " on, were not inserted.") ^0
draw(t)
def ask_key(prompt):
while True:
trim(input(prompt)) => answer
if answer == "":
return [False, 0]
key_of(answer) => k
if k[0]:
return k
"Type one whole number from -999 to 999." ^0
def delete_key(t):
ask_key("key to delete> ") => k
if not k[0]:
"Cancelled." ^0
return
tree.delete(t, k[1]) => r
if len(r) == 0:
(str(k[1]) + " is not in the tree.") ^0
return
if r[0] == 0:
("Deleted " + str(k[1]) + ", a leaf.") ^0
elif r[0] == 1:
("Deleted " + str(k[1]) + "; its one child took its place.") ^0
else:
("Deleted " + str(k[1]) + ". It had two children, so " + str(r[1]) + " - the smallest key on its right - moved up into its place.") ^0
draw(t)
def search_key(t):
ask_key("key to search for> ") => k
if not k[0]:
"Cancelled." ^0
return
tree.search(t, k[1]) => r
if r[0]:
("Found " + str(k[1]) + " after " + str(len(r[1])) + " steps: " + joined(r[1], " -> ") + ".") ^0
elif len(r[1]) == 0:
"The tree is empty." ^0
else:
r[1][len(r[1]) - 1] => last
"left" => side
if k[1] > last:
"right" => side
(str(k[1]) + " is not in the tree: " + joined(r[1], " -> ") + ", and " + str(last) + " has no child on the " + side + ", where it would go.") ^0
def walks(t):
if t[3] == -1:
"The tree is empty." ^0
return
keys(t) => ks
("In order: " + joined(ks, " ")) ^0
("Pre-order: " + joined(tree.pre_order(t, t[3], []), " ")) ^0
("Post-order: " + joined(tree.post_order(t, t[3], []), " ")) ^0
(str(len(ks)) + " keys, height " + str(tree.height(t, t[3])) + ", smallest " + str(ks[0]) + ", largest " + str(ks[len(ks) - 1]) + ".") ^0
def sample():
# The corpus case's keys, in its order.
tree.new_tree() => t
for v in [50, 30, 70, 20, 40, 60, 80, 35]:
tree.insert(t, v)
"The sample: 50 30 70 20 40 60 80 35, inserted in that order." ^0
return t
"== Binary search tree ==" ^0
"Smaller keys go left, larger keys right. The tree is drawn on its side: right is up." ^0
tree.new_tree() => t
True => running
while running:
"" ^0
"1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit" ^0
trim(input("choice> ")) => choice
if choice == "1":
insert_keys(t)
elif choice == "2":
delete_key(t)
elif choice == "3":
search_key(t)
elif choice == "4":
walks(t)
elif choice == "5":
draw(t)
elif choice == "6":
sample() => t
draw(t)
elif choice == "7":
tree.new_tree() => t
"The tree is empty now." ^0
elif choice == "8":
False => running
else:
"Pick a number from 1 to 8." ^0
"Bye." ^0
Python projection (main.py)
import tree
def trim(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def words(s):
out = []
word = ""
for c in s + " ":
if c == " " or c == ",":
if word != "":
out = out + [word]
word = ""
else:
word = word + c
return out
def key_of(s):
digits = s
sign = 1
if len(s) > 1 and s[0] == "-":
digits = s[1:len(s)]
sign = -1
if digits == "" or len(digits) > 3:
return [False, 0]
n = 0
for c in digits:
if not (c >= "0" and c <= "9"):
return [False, 0]
n = n * 10 + int(c)
return [True, sign * n]
def joined(xs, sep):
s = ""
for x in xs:
if s != "":
s = s + sep
s = s + str(x)
return s
def keys(t):
return tree.in_order(t, t[3], [])
def draw(t):
if t[3] == -1:
print("The tree is empty.")
return
for line in tree.sideways(t, t[3], 0, []):
print(line)
def insert_keys(t):
ws = words(trim(input("keys to insert (-999 to 999)> ")))
if len(ws) == 0:
print("Cancelled.")
return
values = []
for w in ws:
k = key_of(w)
if not k[0]:
print("Not a key from -999 to 999: " + w + ". Nothing was inserted.")
return
values = values + [k[1]]
added = []
there = []
k = 0
while k < len(values) and len(keys(t)) < 40:
if tree.insert(t, values[k]):
added = added + [values[k]]
else:
there = there + [values[k]]
k = k + 1
if len(added) > 0:
print("Inserted " + joined(added, " ") + ".")
if len(there) > 0:
print("Already in the tree: " + joined(there, " ") + ".")
rest = len(values) - k
if rest == 1:
print("The tree holds 40 keys, the most it takes; the last key typed, " + str(values[k]) + ", was not inserted.")
elif rest > 1:
print("The tree holds 40 keys, the most it takes; the last " + str(rest) + " keys typed, from " + str(values[k]) + " on, were not inserted.")
draw(t)
def ask_key(prompt):
while True:
answer = trim(input(prompt))
if answer == "":
return [False, 0]
k = key_of(answer)
if k[0]:
return k
print("Type one whole number from -999 to 999.")
def delete_key(t):
k = ask_key("key to delete> ")
if not k[0]:
print("Cancelled.")
return
r = tree.delete(t, k[1])
if len(r) == 0:
print(str(k[1]) + " is not in the tree.")
return
if r[0] == 0:
print("Deleted " + str(k[1]) + ", a leaf.")
elif r[0] == 1:
print("Deleted " + str(k[1]) + "; its one child took its place.")
else:
print("Deleted " + str(k[1]) + ". It had two children, so " + str(r[1]) + " - the smallest key on its right - moved up into its place.")
draw(t)
def search_key(t):
k = ask_key("key to search for> ")
if not k[0]:
print("Cancelled.")
return
r = tree.search(t, k[1])
if r[0]:
print("Found " + str(k[1]) + " after " + str(len(r[1])) + " steps: " + joined(r[1], " -> ") + ".")
elif len(r[1]) == 0:
print("The tree is empty.")
else:
last = r[1][len(r[1]) - 1]
side = "left"
if k[1] > last:
side = "right"
print(str(k[1]) + " is not in the tree: " + joined(r[1], " -> ") + ", and " + str(last) + " has no child on the " + side + ", where it would go.")
def walks(t):
if t[3] == -1:
print("The tree is empty.")
return
ks = keys(t)
print("In order: " + joined(ks, " "))
print("Pre-order: " + joined(tree.pre_order(t, t[3], []), " "))
print("Post-order: " + joined(tree.post_order(t, t[3], []), " "))
print(str(len(ks)) + " keys, height " + str(tree.height(t, t[3])) + ", smallest " + str(ks[0]) + ", largest " + str(ks[len(ks) - 1]) + ".")
def sample():
t = tree.new_tree()
for v in [50, 30, 70, 20, 40, 60, 80, 35]:
tree.insert(t, v)
print("The sample: 50 30 70 20 40 60 80 35, inserted in that order.")
return t
print("== Binary search tree ==")
print("Smaller keys go left, larger keys right. The tree is drawn on its side: right is up.")
t = tree.new_tree()
running = True
while running:
print("")
print("1) insert 2) delete 3) search 4) walks 5) draw 6) sample 7) clear 8) quit")
choice = trim(input("choice> "))
if choice == "1":
insert_keys(t)
elif choice == "2":
delete_key(t)
elif choice == "3":
search_key(t)
elif choice == "4":
walks(t)
elif choice == "5":
draw(t)
elif choice == "6":
t = sample()
draw(t)
elif choice == "7":
t = tree.new_tree()
print("The tree is empty now.")
elif choice == "8":
running = False
else:
print("Pick a number from 1 to 8.")
print("Bye.")
tree.eml
eml# P052 binary search tree - the tree is the corpus case binary-search-tree's
# three parallel lists, indexed by node number with -1 for "no child":
# [values, lefts, rights, root]. Smaller keys go left, larger keys right,
# and a key is in the tree at most once. A deleted node's slot is simply
# no longer linked; nothing is moved.
def new_tree():
return [[], [], [], -1]
def added_node(t, key):
len(t[0]) => k
t[0] + [key] => t[0]
t[1] + [-1] => t[1]
t[2] + [-1] => t[2]
return k
def insert(t, key):
# True when key was added, False when it was there already.
if t[3] == -1:
added_node(t, key) => t[3]
return True
t[3] => n
while True:
if key == t[0][n]:
return False
if key < t[0][n]:
if t[1][n] == -1:
added_node(t, key) => t[1][n]
return True
t[1][n] => n
else:
if t[2][n] == -1:
added_node(t, key) => t[2][n]
return True
t[2][n] => n
def search(t, key):
# [found, the keys passed on the way down].
[] => path
t[3] => n
while n != -1:
path + [t[0][n]] => path
if key == t[0][n]:
return [True, path]
if key < t[0][n]:
t[1][n] => n
else:
t[2][n] => n
return [False, path]
def relink(t, parent, old, new):
# Points whatever pointed at node old - the root, or a child link of
# parent - at node new instead.
if parent == -1:
new => t[3]
elif t[1][parent] == old:
new => t[1][parent]
else:
new => t[2][parent]
def delete(t, key):
# Returns [] when key is not in the tree, otherwise [children, key moved
# up]: a node with no child or one child is cut out and its child (if
# any) takes its place; a node with two children takes the key of its
# successor - the smallest key on its right - and that successor, which
# has no left child, is cut out instead.
-1 => parent
t[3] => n
while n != -1 and t[0][n] != key:
n => parent
if key < t[0][n]:
t[1][n] => n
else:
t[2][n] => n
if n == -1:
return []
if t[1][n] != -1 and t[2][n] != -1:
n => sp
t[2][n] => s
while t[1][s] != -1:
s => sp
t[1][s] => s
t[0][s] => t[0][n]
relink(t, sp, s, t[2][s])
return [2, t[0][n]]
t[1][n] => child
0 => kids
if child != -1:
1 => kids
else:
t[2][n] => child
if child != -1:
1 => kids
relink(t, parent, n, child)
return [kids, key]
def in_order(t, n, out):
# Left subtree, the node, right subtree: the keys in sorted order.
if n == -1:
return out
in_order(t, t[1][n], out) => out
out + [t[0][n]] => out
return in_order(t, t[2][n], out)
def pre_order(t, n, out):
# The node before its subtrees: inserting the keys in this order builds
# the same tree again.
if n == -1:
return out
out + [t[0][n]] => out
pre_order(t, t[1][n], out) => out
return pre_order(t, t[2][n], out)
def post_order(t, n, out):
# Both subtrees before the node: an order in which every node can be
# taken away after its children.
if n == -1:
return out
post_order(t, t[1][n], out) => out
post_order(t, t[2][n], out) => out
return out + [t[0][n]]
def height(t, n):
# Levels: an empty tree has height 0, a lone root 1.
if n == -1:
return 0
height(t, t[1][n]) => a
height(t, t[2][n]) => b
if a > b:
return a + 1
return b + 1
def sideways(t, n, depth, lines):
# The tree turned on its side: the right subtree above its node, the
# left below, four spaces for each level down.
if n == -1:
return lines
sideways(t, t[2][n], depth + 1, lines) => lines
lines + [" " * depth + str(t[0][n])] => lines
return sideways(t, t[1][n], depth + 1, lines)
Python projection (tree.py)
def new_tree():
return [[], [], [], -1]
def added_node(t, key):
k = len(t[0])
t[0] = t[0] + [key]
t[1] = t[1] + [-1]
t[2] = t[2] + [-1]
return k
def insert(t, key):
if t[3] == -1:
t[3] = added_node(t, key)
return True
n = t[3]
while True:
if key == t[0][n]:
return False
if key < t[0][n]:
if t[1][n] == -1:
t[1][n] = added_node(t, key)
return True
n = t[1][n]
else:
if t[2][n] == -1:
t[2][n] = added_node(t, key)
return True
n = t[2][n]
def search(t, key):
path = []
n = t[3]
while n != -1:
path = path + [t[0][n]]
if key == t[0][n]:
return [True, path]
if key < t[0][n]:
n = t[1][n]
else:
n = t[2][n]
return [False, path]
def relink(t, parent, old, new):
if parent == -1:
t[3] = new
elif t[1][parent] == old:
t[1][parent] = new
else:
t[2][parent] = new
def delete(t, key):
parent = -1
n = t[3]
while n != -1 and t[0][n] != key:
parent = n
if key < t[0][n]:
n = t[1][n]
else:
n = t[2][n]
if n == -1:
return []
if t[1][n] != -1 and t[2][n] != -1:
sp = n
s = t[2][n]
while t[1][s] != -1:
sp = s
s = t[1][s]
t[0][n] = t[0][s]
relink(t, sp, s, t[2][s])
return [2, t[0][n]]
child = t[1][n]
kids = 0
if child != -1:
kids = 1
else:
child = t[2][n]
if child != -1:
kids = 1
relink(t, parent, n, child)
return [kids, key]
def in_order(t, n, out):
if n == -1:
return out
out = in_order(t, t[1][n], out)
out = out + [t[0][n]]
return in_order(t, t[2][n], out)
def pre_order(t, n, out):
if n == -1:
return out
out = out + [t[0][n]]
out = pre_order(t, t[1][n], out)
return pre_order(t, t[2][n], out)
def post_order(t, n, out):
if n == -1:
return out
out = post_order(t, t[1][n], out)
out = post_order(t, t[2][n], out)
return out + [t[0][n]]
def height(t, n):
if n == -1:
return 0
a = height(t, t[1][n])
b = height(t, t[2][n])
if a > b:
return a + 1
return b + 1
def sideways(t, n, depth, lines):
if n == -1:
return lines
lines = sideways(t, t[2][n], depth + 1, lines)
lines = lines + [" " * depth + str(t[0][n])]
return sideways(t, t[1][n], depth + 1, lines)