Binary tree from nested dictionary in Python

Question

How can I build a binary tree given a nested dictionary? Ideally, I want access to the root to then traverse the tree in a regular depth-first or breadth-first fashion.

I am not super concerned with efficiency when building the tree from the nested dictionary in terms of time or space so I don't mind using additional data structures in the process. My main focus is a comprehensive and intuitive solution. I have no idea where to start at the moment so any help is greatly appreciated.

class Vertex:
    """Vertex object in a binary tree."""

    def __init__(self):
        """Initialize Vertex object.

        Fields
        ----------
        value : int
            The value of node v
        left : None
            The left child of node v
        right : None
            The right child of node v
        """
        self.value = None
        self.left = None
        self.right = None


def dict_to_binary_tree(data):
    """Implementation here."""
    return root


if __name__ == '__main__':

    t = {
        "value": 1,
        "left": {
            "value": 2,
            "left": {
                "value": 3,
                "left": None,
                "right": None
            },
            "right": {
                "value": 4,
                "left": None,
                "right": None
            }
        },
        "right": {
            "value": 2,
            "left": {
                "value": 4,
                "left": None,
                "right": None
            },
            "right": {
                "value": 3,
                "left": None,
                "right": None
            }
        }
    }

    root = dict_to_binary_tree(t)

    # traverse tree i.e. dfs(root), bfs(root)

Here is what the binary tree looks like:

What problem exactly did you encounter while trying to code this? As it is currently presented, your question looks like "write the code for me". Please read https://meta.stackoverflow.com/questions/334822/how-do-i-ask-and-answer-homework-questions — Thierry Lathuille, Sep 26 '21 at 18:23
I think your `Vertex.__init__` method should have a certain three parameters. — BrianO, Sep 26 '21 at 18:29
There is no question in your question. See [ask] and how to create a [mcve]. — Peter Wood, Sep 26 '21 at 18:52
Edit: I have made the question in the post explicit now, thank you for your help. — Gonzo, Sep 27 '21 at 14:27

score 1 · Answer 1 · answered Sep 26 '21 at 18:58

You should make your Vertex constructor a bit more versatile so that it can use arguments to initialise the attributes.

Like this:

class Vertex:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

Then your function can be recursive, like this:

def dict_to_binary_tree(data):
    return data and Vertex(
            data["value"], 
            dict_to_binary_tree(data["left"]), 
            dict_to_binary_tree(data["right"])
        )

To have a simple depth first iteration, define __iter__ on your Node class:

class Vertex:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def __iter__(self):
        yield self.value
        if self.left:
            yield from self.left
        if self.right:
            yield from self.right

And now your main code can do this:

root = dict_to_binary_tree(t)
print(*root)  # will print values in depth-first, pre-order

score 1 · Accepted Answer · answered Sep 26 '21 at 20:48

A recursive function going through the dictionary should do the job nicely:

def VertexFromDict(d):
    if not d: return None
    v       = Vertex()
    v.value = d['value']
    v.left  = VertexFromDict(d.get('left'))
    v.right = VertexFromDict(d.get('right'))
    return v

output:

root = VertexFromDict(t)
printBTree(root,lambda v:(str(v.value),v.left,v.right))

      1
   __/ \_
  2      2
 / \    / \
3   4  4   3

Note: The printBTree function I used to print the tree can be found here.

Binary tree from nested dictionary in Python

2 Answers2