Inorder traversal between two binary tree nodes
The inorder traversal is a well-known algorithm used to visit nodes in a binary tree. It follows a left-root-right traversal order, meaning that it first visits the left subtree, then the root node, and finally the right subtree. The problem at hand involves performing an inorder traversal between two given nodes in a binary tree. We aim to find and print all the nodes that lie between the two given nodes in the inorder traversal order.

Problem Statement
Given a binary tree and two nodes, n1 and n2, we need to find and print all the nodes that lie between n1 and n2 (inclusive) in the inorder traversal order. If either n1 or n2 does not exist in the tree, we should indicate that the given node pair does not exist.
Example:
Consider the following binary tree:
4 / \ / \ 12 7 / \ \ 2 3 1 / \ / 6 8 5 / \ 9 10
For this tree, we will perform several test cases:
- Test case A: Find the nodes between 2 and 10. Expected output: 12 9 6 3 8
- Test case B: Find the nodes between 8 and 5. Expected output: 10 4 7
- Test case C: Find the nodes between 1 and 6. Expected output: 3 8 10 4 7 5
- Test case D: Find the nodes between 3 and 6. Expected output: None (no nodes exist between them)
- Test case E: Find the nodes between 3 and 11. Expected output: Given node pair (3, 11) does not exist
Algorithm and Pseudocode
Now, let's discuss the algorithm and pseudocode to solve this problem.
Algorithm:
- Start with the root of the binary tree.
- Recursively perform an inorder traversal of the binary tree.
- During the traversal, keep track of the two given nodes, n1 and n2.
- If either n1 or n2 is found, set a flag accordingly.
- If the flag values are different, it means we have encountered both nodes. Print the current node and set a status flag.
- Continue the traversal until all nodes have been visited.
- If the status flag is not set, print "None" to indicate that no nodes exist between n1 and n2.
Pseudocode:
function betweenInorder(node, n1, n2, flag):
if node is not null:
betweenInorder(node.left, n1, n2, flag)
if n1 == node.data and flag[0] == 0:
flag[0] = 1
else if n2 == node.data and flag[1] == 0:
flag[1] = 1
else if flag[0] != flag[1]:
set status flag to 1
print node.data
betweenInorder(node.right, n1, n2, flag)
function nodeInorder(ref, n1, n2):
if ref.root is null:
return
if findNode(ref.root, n1) and findNode(ref.root, n2):
initialize flag[2] with zeros
set ref.status to 0
print "Inorder between (n1,n2) is"
betweenInorder(ref.root, n1, n2, flag)
if ref.status is 0:
print "None"
else:
print "Given node pair (n1,n2) does not exist"
Program Solution
-
1) Inorder traversal between two nodes in a binary tree in java
2) Inorder traversal between two nodes in a binary tree in c++
3) Inorder traversal between two nodes in a binary tree in c
4) Inorder traversal between two nodes in a binary tree in c#
5) Inorder traversal between two nodes in a binary tree in vb.net
6) Inorder traversal between two nodes in a binary tree in php
7) Inorder traversal between two nodes in a binary tree in node js
8) Inorder traversal between two nodes in a binary tree in typescript
9) Inorder traversal between two nodes in a binary tree in python
10) Inorder traversal between two nodes in a binary tree in ruby
11) Inorder traversal between two nodes in a binary tree in scala
12) Inorder traversal between two nodes in a binary tree in swift
13) Inorder traversal between two nodes in a binary tree in kotlin
14) Inorder traversal between two nodes in a binary tree in golang
Time Complexity
The time complexity of this solution depends on the size of the binary tree. Let's denote n as the number of nodes in the tree.
The inorder traversal itself takes O(n) time, as we need to visit each node exactly once. Additionally, the findNode
function has a time complexity of O(n) in the worst case, as it searches for a given node in the binary tree.
Therefore, the overall time complexity of this solution is O(n), where n represents the number of nodes in the binary tree.
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