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.

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.

Categories
Relative Post