Binary tree from nested dictionary-CodePudding

I would like to 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.

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:

CodePudding user response：

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

CodePudding user response：

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.