CODEWITHSUNDEEP
pythonpython-3.xdata-structuresbinary-tree
user9352220
user9352220

Reputation: 95

How to create a specific Binary Tree?

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.

Upvotes: 3

Views: 212

Answers (1)

chepner
chepner

Reputation: 531175

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']

Upvotes: 1

Related Questions