# Deepest right leaf node in a binary tree | Iterative approach

Given a Binary Tree, find the deepest leaf node that is right child of its parent. For example, consider the following tree. The deepest right leaf node is the node with value 10.

Examples:

```Input :
1
/
2     3
/
4 5    6

7    8
/
9        10

Output : 10
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea is similar to Method 2 of level order traversal

Traverse the tree level by level and while pushing right child to queue, check if it is leaf node, if it’s leaf node, then update the result and since we are traversing level by level, the last stored right leaf will be the deepest right leaf node.

## C++

 `// CPP program to find deepest right leaf ` `// node of binary tree ` `#include ` `using` `namespace` `std; ` `  `  `// tree node ` `struct` `Node { ` `    ``int` `data; ` `    ``Node *left, *right; ` `}; ` `  `  `// returns a new tree Node ` `Node* newNode(``int` `data) ` `{ ` `    ``Node* temp = ``new` `Node(); ` `    ``temp->data = data; ` `    ``temp->left = temp->right = NULL; ` `    ``return` `temp; ` `} ` `  `  `// return the deepest right leaf node ` `// of binary tree ` `Node* getDeepestRightLeafNode(Node* root) ` `{ ` `    ``if` `(!root) ` `        ``return` `NULL; ` `  `  `    ``// create a queue for level order traversal ` `    ``queue q; ` `    ``q.push(root); ` `  `  `    ``Node* result = NULL; ` `  `  `    ``// traverse until the queue is empty ` `    ``while` `(!q.empty()) { ` `        ``Node* temp = q.front(); ` `        ``q.pop(); ` `  `  `         `  `        ``if` `(temp->left) { ` `            ``q.push(temp->left); ` `        ``} ` `         `  `        ``// Since we go level by level, the last  ` `        ``// stored right leaf node is deepest one  ` `        ``if` `(temp->right){ ` `            ``q.push(temp->right); ` `            ``if` `(!temp->right->left && !temp->right->right) ` `                ``result = temp->right; ` `        ``} ` `    ``} ` `    ``return` `result; ` `} ` `  `  `// driver program ` `int` `main() ` `{ ` `    ``// construct a tree ` `    ``Node* root = newNode(1); ` `    ``root->left = newNode(2); ` `    ``root->right = newNode(3); ` `    ``root->left->right = newNode(4); ` `    ``root->right->left = newNode(5); ` `    ``root->right->right = newNode(6); ` `    ``root->right->left->right = newNode(7); ` `    ``root->right->right->right = newNode(8); ` `    ``root->right->left->right->left = newNode(9); ` `    ``root->right->right->right->right = newNode(10); ` `  `  `    ``Node* result = getDeepestRightLeafNode(root); ` `    ``if` `(result) ` `        ``cout << ``"Deepest Right Leaf Node :: "` `             ``<< result->data << endl; ` `    ``else` `        ``cout << ````"No result, right leaf not found "````; ` `    ``return` `0; ` `} `

## Python3

# Python3 program to find closest
# value in Binary search Tree

_MIN = -2147483648
_MAX = 2147483648

# Helper function that allocates a new
# node with the given data and None
# left and right poers.
class newnode:

# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None

# utility function to return level
# of given node
def getDeepestRightLeafNode(root) :

if (not root):
return None

# create a queue for level
# order traversal
q = []
q.append(root)

result = None

# traverse until the queue is empty
while (len(q)):
temp = q[0]
q.pop(0)

if (temp.left):
q.append(temp.left)

# Since we go level by level, the last
# stored right leaf node is deepest one
if (temp.right):
q.append(temp.right)
if (not temp.right.left and
not temp.right.right):
result = temp.right

return result

# Driver Code
if __name__ == ‘__main__’:

# create a binary tree
root = newnode(1)
root.left = newnode(2)
root.right = newnode(3)
root.left.right = newnode(4)
root.right.left = newnode(5)
root.right.right = newnode(6)
root.right.left.right = newnode(7)
root.right.right.right = newnode(8)
root.right.left.right.left = newnode(9)
root.right.right.right.right = newnode(10)

result = getDeepestRightLeafNode(root)
if result:
print(“Deepest Right Leaf Node ::”,
result.data)
else:

# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

Output:

```Deepest Right Leaf Node :: 10
```

Time Complexity : O(n)

Mandeep Singh

Tree Tree