0

A binary tree is given where each node has a limited and undefined number of children. In the node structure, there are no references to the parent node. A corresponding X value is given to any node in the tree. If values are unique in the tree, find the value of the parent node of the node with the value X. Specifications:

1: Build a structure to represent one such tree.

2: Build a recursive function to find the value of the parent.

I tried looking up online about a solution as i have no experience with this type of exercise and came up with no solution. I dont really know what to do.

PM 77-1
  • 12,933
  • 21
  • 68
  • 111
F481000
  • 1
  • Would you know how to find a value in a binary tree in general? – PM 77-1 Nov 03 '22 at 18:46
  • Yeah, we start searching from the root node then if the data is less we search in the left subtree if not we search in the right. It's just that i dont really have any coding experience in binary algorithms and structers and have no idea how to do this. – F481000 Nov 03 '22 at 18:59

1 Answers1

1

Hope you are not cheating in a test.
Edit: This is for n-ary tree rather than binary tree.

This can be done with basic tree traversal with back-tracking.
Here's a Depth-First-Search based Implementation:

class Tree(object):
    "Generic tree node. Adapted from https://stackoverflow.com/a/28015122/7562633 "
    def __init__(self, value, children=None):
        self.value = value
        self.children = []
        if children is not None:
            for child in children:
                self.add_child(child)
    def add_child(self, node):
        assert isinstance(node, Tree)
        self.children.append(node)
    def __repr__(self):
        return str(self.value)


def dfs_find_parent(tree, search_value, parent=None):
    """
    Given a subTree `tree` find parent of the `search_value`.
    In a DFS manner!
    If the root node itself is search_value, return parent
    """
    # terminal case that root of subTree is the target value
    if tree.value == search_value:
        return parent
    # otherwise look for target value in the children
    for child in tree.children:
        found = dfs_find_parent(child, search_value, tree)
        if found is not None:
            return found
    # no match in this tree
    return None
    

# DRIVER CODE: 
#    0
#   /|\
#  1 2 3
#     / \
#    4   5
t = Tree('0', [Tree('1'),
               Tree('2'),
               Tree('3', [Tree('4'),
                          Tree('5')])])
for i in range(7):
    print("Parent of {} is {}".format(i, dfs_find_parent(t, str(i))))

Output:
Parent of 0 is None
Parent of 1 is 0
Parent of 2 is 0
Parent of 3 is 0
Parent of 4 is 3
Parent of 5 is 3
Parent of 6 is None

smartm13
  • 11
  • 4