CODEWITHSUNDEEP
pythonrecursiondata-structurestreebinary-tree
asciilatin
asciilatin

Reputation: 11

In binary tree insertion, only the left tree is right. The right tree is wrong

I have a btree class and an insert function, to insert nodes to a tree, breadth wise. But the tree isn't inserting nodes to the right.

I'm creating the root node. The insert function inserts left and right nodes to the root correctly.

Then recursively, I try to insert two nodes to the left node and two to the right node. But in this step, all nodes are added to the left only. Nodes get added to a None parent as well.

I know, I'm making a mistake in the last else statement inside insert function. But I've tried many combinations, but all have resulted in some error.

class BinTree(object):
  def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None

  def insert(self,val):
    if self.left is None:
      self.left = BinTree(val)
    elif self.right is None:
      self.right = BinTree(val)
    elif self.left:
      self.left.insert(val)
    else:
      self.right.insert(val)

root = BTree('A')
root.insert('B')
root.insert('C')
root.insert(None)
root.insert('D')
root.insert(None)
root.insert('E')
root.insert('F')

Expected:
                 A
              /     \
             B       C
            /\       /\
        None  D  None  E
             /
            F

Getting:
                 A
              /     \
             B       C
            / \
        None   D
         /  \
     None    E
       /
      F

Upvotes: 1

Views: 815

Answers (3)

dWinder
dWinder

Reputation: 11642

Your tree is build exactly as your code suggest.

The insert function checks if there is an empty child and set if it found one - else it is going recursively to the left (regardless of its length) and that is exactly the tree you get.

Second, your output is not clear - what do you mean by adding None?

In order to achieve building of full tree you need to keep count of your elements.

Then we will be able the use the division on the count by 2 to find the right path (taking leaf or right) till reaching the right leaf. Add self.cnt = 1 to the constructor. Using this for pseudocode for insert:

insert:
    cnt = self.cnt++ // Increase the count and get the new value
    while (cnt > 0) {
        path.push(cnt % 2 == 0 ? left : right) // If even, go left. Else go right.
        cnt = cnt / 2
    }
    path.reverse // We need to start from the last element we pushed
    current = head
    while (path not empty)
        current = current.path.pop
    current = val

Try to look at the tree number to understand it better:

             1
           /   \
          2     3
         / \   /  \
        5   6 7    8

Upvotes: 0

trincot
trincot

Reputation: 349956

Your code will traverse to the left as soon as it finds a node there that is not None, which is like a depth-first search (DFS). So the code does not look further at the right side to see if there are still some vacancies to be filled there, but goes left anyway. This results in the bias towards the left of your tree.

Instead, you should use a breadth-first search (BFS) to search for the next vacancy in the tree, so in breadth first order. For that you could use a separate method that will perform this BFS and returns the position of the vacancy (by providing its parent node and which side the new child node should be on).

Here is how that new method would look:

def next_free(self):
    queue = [self]
    while len(queue):
        node = queue.pop(0) # Here you get the nodes in BFS order
        if node.val is None: # Cannot have children
            continue
        for side, child in enumerate((node.left, node.right)):
            if child is None: # Found the first vacancy in BFS order!
                return node, side
            queue.append(child)

Now the insert method becomes trivial:

def insert(self,val):
    node, side = self.next_free()
    if side == 0:
        node.left = Node(val)
    else:
        node.right = Node(val)

You can see it run on repl.it.

Upvotes: 0

Tom Slabbaert
Tom Slabbaert

Reputation: 22276

You can't really get the result you want with recursion with the current field you save. Each node only "knows" its current state, and that's why the right side of your tree will forever remain at depth 1.

One solution that comes to mind is adding a right children and left children amount field. This will help tracking the balance. It would look like this:

 class Node(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.right_count = 0
        self.left_count = 0
        self.even_depth = True
        self.needed_to_even = 1

    def insert(self, val):
        if self.left is None:
            self.left = Node(val)
            self.left_count += 1
        elif self.right is None:
            self.right = Node(val)
            self.right_count += 1
        elif self.left_count > self.right_count + self.needed_to_even or not self.even_depth:
            self.even_depth = False
            if self.left_count == self.right_count:
                self.needed_to_even *= 2
                self.even_depth = True
            self.right.insert(val)
            self.right_count += 1
        else:
            self.left.insert(val)
            self.left_count += 1

Upvotes: -1

Related Questions