Construct Binary tree using dictionary

Question

I have a dictionary of nodes and their children but I am stuck at inserting the children's nodes to construct a binary tree. I am using the binary tree to get the preorder traversal and inorder traversal.

input: Each key pair represent: root:(left child, right child) and can be in any order {6:(None,None), 10:(2,6), 2:(None,None), 3:(14,None),8:(10,3)}

Output Tree

Binary Tree

I wanted the tree to be in class format (e.g. root.left will return 10, root.left.right will return 6. But my code is not looking for the root node which should be 8:(10,3) and collect all children. How can i enhance the code?

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

   # Compare the new key with the left and right node
   def insert(self, key, vals):
        
        if self.key == None:
           self.key = key
           self.left = vals[0]
           self.right = vals[1]
       
        # else if left is equal to key
        elif self.left == key:
           self.key = key
           self.left = vals[0]
           self.right = vals[1]
        
        # else if right is equal to key 
        elif: 
           self.key = key
           self.left = vals[0]
           self.right = vals[1]

There are two problems here. First, the insert location might be far down the tree. You need to search recursively to find the insert location. And where do you create the new node? Second, with your examples, you will be replacing the root node several times. That's probably not part of the Node class and will be separate. — Tim Roberts
– Tim Roberts, Commented Feb 14, 2023 at 2:26
Hi @TimRoberts Thanks for the response. As i am trying to find the preorder traversal and in order traversal of that dictionary, hence i am building the binary tree. Else are there other better ways of doing so? — Gab
– Gab, Commented Feb 14, 2023 at 2:27
Your data structure is fine, but that's not how you do an insert. You don't ever change the existing key. Instead, you create a NEW Node and find a place for it, either as the new root or at another location. — Tim Roberts
– Tim Roberts, Commented Feb 14, 2023 at 2:38
Perhaps you should do the traversal code first and worry about the class later. How will you decide which element is the root? — Tim Roberts
– Tim Roberts, Commented Feb 14, 2023 at 2:52
The root's key will never exist in any of the children's nodes. That's how I find 8:(10,3) to be my root — Gab
– Gab, Commented Feb 14, 2023 at 3:02

Tim Roberts · Accepted Answer · 2023-02-14 04:26:13Z

The data structure they gave you is a perfectly fine way to store a binary tree. There's no particular need to convert it to objects. You could have a Tree object and have these all be methods of that class, but I'm not sure that's really better.

from collections import defaultdict

tree = {6:(None,None), 10:(2,6), 2:(None,None), 3:(14,None),8:(10,3)}

def find_root(tree):
    nodes = defaultdict(int)
    for k,(l,r) in tree.items():
        if l:
            nodes[l] += 1
        if r:
            nodes[r] += 1
    for k in tree:
        if k not in nodes:
            return k

def pre_traverse(tree,node):
    if not node:
        return
    print(node)
    if not node in tree:
        return
    pre_traverse(tree,tree[node][0])
    pre_traverse(tree,tree[node][1])

def in_traverse(tree,node):
    if not node:
        return
    if not node in tree:
        print(node)
        return
    in_traverse(tree,tree[node][0])
    print(node)
    in_traverse(tree,tree[node][1])

root = find_root(tree)
print("in-order traversal:")
in_traverse(tree,root)
print("pre-order traversal:")
pre_traverse(tree,root)

Output:

in-order traversal:
2
10
6
8
14
3
pre-order traversal:
8
10
2
6
3
14

Collectives™ on Stack Overflow

Construct Binary tree using dictionary

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related