would like to convert it to a list of all nodes with keys at depth
1 (root), depth 2 (children of root), and so on. At each depth, the
keys must appear from left to right.
The example below will clarify the problem.
Consider the BST below as input:
- You Are Given A Binary Search Tree Whose Keys Are Numbers We Would Like To Convert It To A List Of All Nodes With Keys 1 (24.13 KiB) Viewed 36 times
Your algorithm should work in time that is linear in the number
of nodes of the tree.
For your convenience, we have given you a binary search tree
data structure class TreeNode with functions for insertion. Please
complete the implementation of the depthWiseTraverse function.
Note, coding language used is Python
class TreeNode:
# Constructor for tree nodde
def __init__(self, key, parent_node=None):
self.key = key # set the
key
self.parent =
parent_node # set the parent_node
self.left = None # set
the left child to None -- no left child to begin with
self.right = None # set
the right child to None - no right child to begin with.
def is_root(self):
return parent_node ==
None
# Function: insert
# insert a node with key `new_key` into the
current tree.
def insert(self, new_key):
key = self.key
if new_key == key:
print(f'Already inserted key {key}. Ignoring')
elif new_key < key: #
new_key must go into the left subtree
if self.left == None: # no left child?
new_node = TreeNode(new_key, self) # create one with self as
parent
self.left = new_node # set the left pointer
else:
self.left.insert(new_key) # recursively call insert on left
subtree
else: # new_key
must go into the right subtree.
assert new_key > key
if self.right == None: # no right child?
new_node = TreeNode(new_key, self) # create one
self.right = new_node
else:
self.right.insert(new_key) # recusively call insert on right
subtree.
# TODO: Implement the function depthWiseTraverse below
def depthWiseTraverse(root_node):
# This function inputs the root node of the
tree.
# root_node is an instance of the TreeNode class
provided to you above
# See description and example above.
# your code here
To check for correctness
def make_tree(insertion_list):
assert len(insertion_list) > 0
root_node = TreeNode(insertion_list[0])
for elt in insertion_list[1:]:
root_node.insert(elt)
return root_node
print('-- Test 1 --')
# Same as the example above
tree1 = make_tree([11, 18, 15, 13, 21, 17, 4])
lst1 = depthWiseTraverse(tree1)
print(lst1)
assert lst1 == [11, 4, 18, 15, 21, 13, 17]
print('-- Test 2 --')
tree2 = make_tree([3, 1, 2, 4, 6, 7])
lst2 = depthWiseTraverse(tree2)
print(lst2)
assert lst2 == [3, 1, 4, 2, 6, 7]
print('-- Test 3 --')
tree3 = make_tree([7, 3, 1, 2, 4, 6, 15, 8, 11, 10, 9])
lst3 = depthWiseTraverse(tree3)
print(lst3)
assert lst3 == [7, 3, 15, 1, 4, 8, 2, 6, 11, 10, 9]
print('All tests passed: 15 points')
4 13 11 15 18 17 21