Creating Binary Tree

Question

Most of the questions I've searched for regarding binary trees shows the implementation of binary search trees, but not binary trees. The terms of a complete binary tree are:

• Either an empty tree or it has 1 node with 2 children, where each child is another Binary Tree.
• All levels are full (except for possibly the last level)
• All leaves on the bottom-most level are as far left as possible.

I've come up with a concept but it doesn't seem to running through the recursion properly -- Does anyone know what I'm doing wrong?

class Node():
 def __init__(self, key):
 self.key = key
 self.left = None
 self.right = None
 def add(self, key): 
 if self.key: 
 if self.left is None: 
 self.left = Node(key) 
 else: 
 self.left.add(key)
 if self.right is None: 
 self.right = Node(key) 
 else: 
 self.right.add(key) 
 else: 
 self.key = key
 return (self.key)

• Teejay Bruno: can you post an example of the code you ran to get your returned tree?
• Jason Liu: Sounds like you need to implement something like a self balancing tree. Maybe start from there?
• NikeDog: stackoverflow.com/questions/34012886/… TeeJay, I used the code from the first answer on this question to help me visualize what was going on
• quamrana: One problem with your code is that after the top of the tree becomes full, you add keys recursively to both legs of the tree.
• NikeDog: what do you mean by this? don't I want to be adding to the left and right legs of the tree?

Answer 1

The problem in your code is that you are adding the same value multiple times. You add the node, and then still recurse deeper, where you do the same.

The deeper problem is that you don't really know where to insert the node before you have reached the bottom level of the tree, and have detected where that level is incomplete. Finding the correct insertion point may need a traversal through the whole tree... which is defeating the speed gain you would expect to get from using binary trees in the first place.

I provide here three solutions, starting with the most efficient:

1. Using a list as tree implementation

For complete trees there is a special consideration to make: if you number the nodes by level, starting with 0 for the root, and within each level from left to right, you notice that the number of a node's parent is (k-1)/2 when its own number is k. In the other direction: if a node with number k has children, then its left child has number k*2+1, and the right child has a number that is one greater.

Because the tree is complete, there will never be gaps in this numbering, and so you could store the nodes in a list, and use the indexes of that list for the node numbering. Adding a node to the tree now simply means you append it to that list. Instead of a Node object, you just have the tree list, and the index in that list is your node reference.

Here is an implementation:

class CompleteTree(list):
 def add(self, key):
 self.append(key)
 return len(self) - 1
 def left(self, i):
 return i * 2 + 1 if i * 2 + 1 < len(self) else -1
 def right(self, i):
 return i * 2 + 2 if i * 2 + 2 < len(self) else -1 
 @staticmethod
 def parent(i):
 return (i - 1) // 2
 def swapwithparent(self, i):
 if i > 0:
 p = self.parent(i)
 self[p], self[i] = self[i], self[p]
 def inorder(self, i=0):
 left = self.left(i)
 right = self.right(i)
 if left >= 0:
 yield from self.inorder(left)
 yield i
 if right >= 0:
 yield from self.inorder(right)
 @staticmethod
 def depth(i):
 return (i + 1).bit_length() - 1

Here is a demo that creates your example tree, and then prints the keys visited in an in-order traversal, indented by their depth in the tree:

tree = CompleteTree()
tree.add(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
for node in tree.inorder():
 print(" " * tree.depth(node), tree[node])

Of course, this means you have to reference nodes a bit different from when you would use a real Node class, but the efficiency gain pays off.

2. Using an extra property

If you know how many nodes there are in a (sub)tree, then from the bit representation of that number, you can know where exactly the next node should be added.

For instance, in your example tree you have 5 nodes. Imagine you want to add a 6 to that tree. The root node would tell you that you currently have 5 and so you need to update it to 6. In binary that is 110. Ignoring the left-most 1-bit, the rest of the bits tell you whether to go left or right. In this case, you should go right (1) and then finally left (0), creating the node in that direction. You can do this iteratively or recursively.

Here is an implementation with recursion:

class Node():
 def __init__(self, key):
 self.key = key
 self.left = None
 self.right = None
 self.count = 1
 def add(self, key):
 self.count += 1
 if self.left is None:
 self.left = Node(key)
 elif self.right is None:
 self.right = Node(key)
 # extract from the count the second-most significant bit:
 elif self.count & (1 << (self.count.bit_length() - 2)):
 self.right.add(key)
 else:
 self.left.add(key)
 def inorder(self):
 if self.left:
 yield from self.left.inorder()
 yield self
 if self.right:
 yield from self.right.inorder()
tree = Node(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
for node in tree.inorder():
 print(node.key)

3. Without extra property

If no property can be added to Node objects, then a more extensive search is needed to find the right insertion point:

class Node():
 def __init__(self, key):
 self.key = key
 self.left = None
 self.right = None
 def newparent(self):
 # Finds the node that should serve as parent for a new node
 # It returns a tuple:
 # if parent found: [-1, parent for new node]
 # if not found: [height, left-most leaf]
 # In the latter case, the subtree is perfect, and its left-most 
 # leaf is the node to be used, unless self is a right child 
 # and its sibling has the insertion point.
 if self.right:
 right = self.right.newparent()
 if right[0] == -1: # found inbalance
 return right
 left = self.left.newparent()
 if left[0] == -1: # found inbalance
 return left
 if left[0] != right[0]:
 return [-1, right[1]] # found inbalance
 # temporary result in perfect subtree
 return [left[0]+1, left[1]]
 elif self.left:
 return [-1, self] # found inbalance
 # temporary result for leaf
 return [0, self]
 def add(self, key):
 _, parent = self.newparent()
 if not parent.left:
 parent.left = Node(key)
 else:
 parent.right = Node(key)
 def __repr__(self):
 s = ""
 if self.left:
 s += str(self.left).replace("\n", "\n ")
 s += "\n" + str(self.key)
 if self.right:
 s += str(self.right).replace("\n", "\n ")
 return s
tree = Node(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
print(tree)

This searches recursively the tree from right to left, to find the candidate parent of the node to be added.

For large trees, this can be improved a bit, by doing a binary-search among paths from root to leaf, based on the length of those paths. But it will still not be as efficient as the first two solutions.

• NikeDog: unfortunately I can't use any lists
• trincot: Why not? If you have restrictions, please mention those in your question. Like: is the Node class fixed? Can you alter it? Must you use such a class? Can you use dictionaries, tuples, sets, lambdas, loops, ...etc, ...etc?
• trincot: Anyway, I added two alternatives to my answer.
• NikeDog: I'm tried to implement #2, but I got an syntax error on the line "elif self.count & (1 << (self.count.bit_length() - 2)):". I tried using my own method as the elif statement to differentiate between the left or right branch, but I'm unable to run the "for node in tree.inorder():" line. Where did you get the variable tree?
• NikeDog: actually this works perfectly, I think it was just some things I changed a little bit while working out the rest of the code. Thanks so much for your help :)

Answer 2

You can use the sklearn Decision trees, as they are able to be set up as binary decision trees as well. link to the documentation here.

Answer 3

You really need to augment your tree in some way. Since this is not a binary search tree, the only real information you have about each node is whether or not it has a left and right child. Unfortunately, this isn't helpful in navigating a complete binary tree. Imagine a complete binary tree with 10 levels. Until the 9th level, every single node has both a left child and a right child, so you have no way of knowing which path to take down to the leaves. So the question is, what information do you add to each node? I would add the count of nodes in that tree.

Maintaining the count is easy, since every time you descend down a subtree you know to add one to the count at that node. What you want to recognize is the leftmost imperfect subtree. Every perfect binary tree has n = 2^k - 1, where k is the number of levels and n is the number of nodes. There are quick and easy ways to check if a number is 1 less than a power of two (see the first answer to this question), and in fact in a complete binary tree every node has at most one child that isn't the root of a perfect binary tree. Follow a simple rule to add nodes:

1. If the left child is None, set root.left = Node(key) and return
2. Else if the right child is None, set root.right = Node(key) and return
3. If one of the children of the current node is the root of an imperfect subtree, make that node the current node (descend down that subtree)
4. Else if the sizes are unequal, make the node with the smaller subtree the current node.
5. Else, make the left child the current node.

By augmenting each node with the size of the subtree rooted there, you have all the information you need at every node to build a recursive solution.

• NikeDog: do you know of any resources where I can check to see if the number is less than the power of two?
• Charles Gleason: I added a link, it's really just a neat trick with bitwise operations. That's for checking powers of two, so to check one less you just do x & (x + 1) == 0 instead of x & (x - 1) == 0
• NikeDog: how would you descend down the subtree after figuring that out?
• trincot: Step four in this algorithm is not always correct. Imagine this tree, listed in BFS order, level by level: [1], [2, 3], [4, 5, null, null]. Now the algo starts at 1: both its children are the root of a perfect subtree, yet the node should be added under the right child, not the left.
• Charles Gleason: Ah, you're very correct. I was trying to avoid doing the bit encoding to make a more recursive solution but now it's starting to get crowded. I would say smaller than leftmost should handle it, thank you!