Posted on by Kalkicode
Code Recursion

Find parent of leaf nodes in binary tree

The problem is to find the parents of all leaf nodes in a binary tree. A binary tree is a tree data structure in which each node can have at most two children, referred to as the left child and the right child. A leaf node is a node with no children, meaning it is the end of a branch in the tree.

Parent of leaf nodes in binary tree

In this context, we want to find and display the parents of all the leaf nodes in the given binary tree.

Pseudocode

leafParent(node, parent)
    if node is not null
        if node is a leaf node
            if parent is null
                print "NULL"
            else
                print parent.data
        else
            leafParent(node.left, node)
            leafParent(node.right, node)

Algorithm Explanation

The leafParent function finds the parents of leaf nodes in the binary tree using recursion. It takes two parameters: node and parent. The variable node represents the current node being visited, while parent represents the parent node of the current node.

The algorithm starts by checking if node is not null. If node is null, it means that there are no more nodes to explore, and the function returns. Otherwise, it proceeds to check if the node is a leaf node, which means it has no left and right children.

If the node is a leaf node, the algorithm prints the data of its parent. If the parent is null, it means the current node is the root of the tree, and there is no parent for the root. In this case, the algorithm prints "NULL" to indicate that there is no parent for the root node. Otherwise, it prints the data of the parent node.

If the node is not a leaf node, the algorithm recursively calls itself on the left and right children of the current node, passing the current node as the parent.

Code Solution

Here given code implementation process.

The time complexity of the provided algorithm is O(N), where N is the number of nodes in the binary tree. This is because the algorithm visits each node exactly once in a depth-first manner, and the number of nodes visited is proportional to the number of nodes in the tree.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment