How to create a specific Binary Tree?

Question

I have just implemented my first Binary Tree:

class BinaryTree:
 def __init__(self, obj):
 self.key = obj
 self.left_c = None
 self.right_c = None
 def insert_left_c(self, new_node):
 if self.left_c == None:
 self.left_c = BinaryTree(new_node)
 else:
 temp = BinaryTree(new_code)
 temp.left_c = self.left_c
 self.left_c = temp
 def insert_right_c(self, new_node):
 if self.right_c == None:
 self.right_c = BinaryTree(new_node)
 else:
 temp = BinaryTree(new_code)
 temp.right_c = self.right_c
 self.right_c = temp
 def set_root(self, obj):
 self.key = obj
 def get_root(self):
 return self.key
 def get_left_c(self):
 return self.left_c
 def get_right_c(self):
 return self.right_c

I am struggling to understand how you actually go about building a tree to ones specifications. As an example, I am trying to build the following tree:

enter image description here

However, I am really struggling to understand / visualize how you build the lower nodes and manipulate their left / right branches.

I though I may be able to do something such as:

binary_tree = BinaryTree('a')
binary_tree.insert_left_c('b')
binary_tree.insert_right_c('d')
binary_tree.insert_right_c('c')
binary_tree.insert_left_c('e')
binary_tree.insert_right_c('f')

But I realize that is nonsensical because I believe I'm creating a unique node for all letters that would be on the same level? I never actually set one to be a child of another(?).

If someone could explain how one should go about solving this, and visualizing similar problems, I would much appreciate it.

• G_M: github.com/joowani/binarytree

Answer 1

Your insert functions only operate on the root, without traversing deeper into the tree. Usually, such a function would insert into a binary search tree, recursing left or right depending on how the value to insert compares to the root of the current tree. For a general binary tree, you would want to pass an explicit list of left/right directions to specify where a new value goes.

It would be simpler to just build the tree explicitly. Start with individual trees for each leaf, then merge them.

trees = {x: BinaryTree(x) for x in 'abcdef'}
binary_tree = trees['a']
binary_tree.left_c = trees['b']
binary_tree.right_c = trees['c']
trees['b'].right_c = trees['d']
trees['c'].left_c = trees['e']
trees['c'].right_c = trees['f']