CODEWITHSUNDEEP
pythonpython-2.7binary-search-tree
genclik27
genclik27

Reputation: 323

Traversing the elements of BST

I have a binary search tree whose nodes are stored in a python dictionary. Here is an example:

BST = {'node1': ['Fail', 'node3'], 'node3': ['Fail', 'Pass'], 'node2': ['Fail', 'node1'], 'node4': ['Fail', 'node2']}

In the dictionary, every key is a parent from BST and the list (value of the key) is the children of that parent with corresponding key from dictionary.

For example:

BST['node1'] =  ['Fail', 'node3']

In this case, 'node1' is the parent of the children ['Fail', node3]. First element of the list, 'Fail' is the left child of the 'node1' and the other element of that list, 'node3' is the right child of the 'node1'.

The edge between left child and its parents has the value of 'yes', and the edge between right child and its parents has the value of 'no'.

Fail and Pass values are the leaves of the BST.

One observation, to be able to find the root; just pick a node and check whether is has a parent. If not, it is the root of the tree. Otherwise check the same thing with the parent of that node.

Here is the corresponding tree with the dictionary:

tree with the dictionary

I think the construction of the tree is clear. Now about my question, I need to find the paths in the format of having FAIL node as its final node and starting with a yes edge. If the first node is not with yes edge, just eliminate it and look for the next one until the yes edge is found to be starting point of that path.

Illustrative example:

example tree

In this BST, valid paths should be:

[[node4,yes], [node1, yes], [node3, yes], FAIL]
[[node4,yes], [node1, no], FAIL]]
[[node2,yes], FAIL]
[[node1,yes], FAIL]
[[node3,yes], FAIL]

Note: If a path is found, no need to look at its sub paths. For example, this is not valid since there is longer path that covers this one:

[[node4,yes], [node3, yes], FAIL].

which is:

[[node4,yes], [node1, yes], [node3, yes], FAIL]

Upvotes: 2

Views: 520

Answers (1)

Siva Cn
Siva Cn

Reputation: 947

It's ugly, to implement the Tree with the Dictionaries, instead use the self referential structure class Node as mentioned below

class Node:
    """Referential Structure used to create new nodes"""
    def __init__(self, data):
        """Constructor."""
        self.data = data
        self.left = None
        self.right = None

This will make your Traversal much easier

please refer: https://github.com/SivaCn/Small-Codes/blob/master/Python/BinarySearchTree.py

Upvotes: 1

Related Questions