# Binary Tree Using Lists¶

In [1]:
def binary_tree(r):
return [r, [], []]

In [2]:
def insert_left(root, new_branch):
t = root.pop(1)

if len(t) > 1:
root.insert(1, [new_branch, t, []])
else:
root.insert(1, [new_branch, [], []])

return root

In [3]:
def insert_right(root, new_branch):
t = root.pop(2)

if len(t) > 1:
root.insert(2, [new_branch, [], t])
else:
root.insert(2, [new_branch, [], []])

return root

In [4]:
def get_root_val(root):
return root[0]

In [5]:
def set_root_val(root, new_val):
root[0] = new_val

In [6]:
def get_left_child(root):
return root[1]

In [7]:
def get_right_child(root):
return root[2]


## Testing Its Use¶

In [8]:
r = binary_tree(3)

In [9]:
r

Out[9]:
[3, [], []]
In [10]:
insert_left(r, 4)

Out[10]:
[3, [4, [], []], []]
In [11]:
insert_right(r, 6)

Out[11]:
[3, [4, [], []], [6, [], []]]
In [12]:
l = get_left_child(r)

In [13]:
l

Out[13]:
[4, [], []]
In [14]:
set_root_val(l, 9)

In [15]:
l

Out[15]:
[9, [], []]
In [16]:
r

Out[16]:
[3, [9, [], []], [6, [], []]]
In [17]:
insert_left(l, 12)

Out[17]:
[9, [12, [], []], []]
In [18]:
l

Out[18]:
[9, [12, [], []], []]
In [19]:
r

Out[19]:
[3, [9, [12, [], []], []], [6, [], []]]
In [20]:
from graphviz import Digraph
from pythonds9.basic.stack import Stack

In [21]:
def viz_tree(r):
"""Visualize a list-based tree data structure

1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
a) Pop the top item from stack.
b) Print the popped item, set current = popped_item->right
c) Go to step 3.
5) If current is NULL and stack is empty then we are done.
"""
stack = Stack()
g = Digraph(node_attr={'shape': 'record', 'height': '.1'})
_id = 0
current_node = r
leftward = True
current_root_num = 0

while True:
if current_node:
stack.push((_id, current_node))

g.node('node{0}'.format(_id), '<f0> |<f1> {0} (#{1})|<f2> '.format(current_node[0], _id))
if _id >= 1:
g.edge('node{0}:f{1}'.format(current_root_num, 0 if leftward else 2),
'node{0}:f1'.format(_id))

leftward = True
current_node = current_node[1]  # left
current_root_num = _id
_id += 1

if current_node == [] and not stack.is_empty():
count, popped_node = stack.pop()
if popped_node[2]:
current_root_num = count
current_node = popped_node[2]  # right
leftward = False

if current_node == [] and stack.is_empty():
break

return g

In [22]:
g = viz_tree(r)

In [23]:
r

Out[23]:
[3, [9, [12, [], []], []], [6, [], []]]
In [24]:
g

Out[24]:

## Importing viz_tree_list from our pythonds9 package¶

In [25]:
from pythonds9.tree.utils import viz_tree_list

In [26]:
g2 = viz_tree_list(r)

In [27]:
g2

Out[27]: