How to create a Binary tree using a dict?

Question

I want to create a binary tree from a dictionary of parents (keys) and their children (values, as tuples (one_child, second_child)):

{1:(2,3), 2:(4,5), 4:(6, None), 3:(7,8), ...}   #they are in random order

The binary tree should be created without using a recursion.

My Node class:

class Node:
    def __init__(self,key):
        self.left = None
        self.right = None
        self.val = key

What was I trying for was: What I tried was:

self.root = self.Node(found_root)
parents = list(dictionary)
p = 0
while (p != len(parents)-1):
    curr_node = self.Node(parents[p], self.Node(dictionary.get(parents[p])[0]),self.Node(dictionary.get(parents[p])[1]))
    p += 1

Ok. So what's your question? Have you written some code that you're having trouble with? — Tom Karzes
– Tom Karzes, Commented Mar 30, 2019 at 16:00
What I tried was: self.root = self.Node(found_root); parents = list(dictionary); p = 0; while (p != len(parents)-1): curr_node = self.Node(parents[p], self.Node(dictionary.get(parents[p])[0]), self.Node(dictionary.get(parents[p])[1])); p += 1; So what was I trying for was creating a huge amount of subtrees and then joining them. -- already appended to the first post — fin1010
– fin1010, Commented Mar 30, 2019 at 16:06

Ajax1234 · Accepted Answer · 2019-03-30 17:16:56Z

You can create a custom insertion method in your Node class, and then the tree creation can be accomplished with a simple iterative pass over the dictionary:

class Node:
   def __init__(self, head = None):
     self.head, self.left, self.right = head, None, None
   def __contains__(self, head):
     if head == self.head:
        return True
     return (False if self.left is None else head in self.left) or (False if self.right is None else head in self.right)
   def insert(self, head, vals):
     if self.head is None:
        self.head, self.left, self.right = head, Node(vals[0]), Node(vals[1])
     elif self.head == head:
        self.left, self.right = Node(vals[0]), Node(vals[1])
     else:
        getattr(self, 'left' if self.left and head in self.left else 'right').insert(head, vals)

n = Node()
d = {1:(2,3), 2:(4,5), 4:(6, None), 3:(7,8)}
for a, b in d.items():
   n.insert(a, b)

This produces the correct tree, as it can be easily shown that the original input can be obtained by traversing the node instance:

def to_dict(_n):
  yield (_n.head, (getattr(_n.left, 'head', None), getattr(_n.right, 'head', None)))
  if _n.left:
    yield from to_dict(_n.left)
  if _n.right:
    yield from to_dict(_n.right)

print(dict(to_dict(n)))

Output:

{1: (2, 3), 2: (4, 5), 4: (6, None), 6: (None, None), None: (None, None), 5: (None, None), 3: (7, 8), 7: (None, None), 8: (None, None)}

Collectives™ on Stack Overflow

How to create a Binary tree using a dict?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related