You have been given a Binary Tree of 'n' nodes, where the nodes have integer values. Your task is to return the In-Order traversal of the given binary tree.
For the given binary tree:
The Inorder traversal will be [5, 3, 2, 1, 7, 4, 6].
The first line contains elements of the tree in the level order form.
The line consists of values of nodes separated by a single space.
In case a node is null, we take -1 in its place.
The input for the above tree is:
1 3 8 5 2 7 -1 -1 -1 -1 -1 -1 -1
Explanation :
Level 1 :
The root node of the tree is 1
Level 2 :
Left child of 1 = 3
Right child of 1 = 8
Level 3 :
Left child of 3 = 5
Right child of 3 = 2
Left child of 8 = 7
Right child of 8 = null (-1)
Level 4 :
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 2 = null (-1)
Right child of 2 = null (-1)
Left child of 7 = null (-1)
Right child of 7 = null (-1)
1
3 8
5 2 7 -1
-1 -1 -1 -1 -1 -1
The output contains 'n' single space-separated integers denoting the node's values in In-Order traversal.
You don't need to print anything, it has already been taken care of. Just implement the given function.
1 2 3 -1 -1 -1 6 -1 -1
2 1 3 6
The given binary tree is shown below:
Inorder traversal of given tree = [2, 1, 3, 6]
1 2 4 5 3 -1 -1 -1 -1 -1 -1
5 2 3 1 4
The given binary tree is shown below:
Inorder traversal of given tree = [5, 2, 3, 1, 4]
The expected time complexity is O(n).
1 <= 'n' <= 10^5
0 <= 'data' <= 10^5
where 'n' is the number of nodes and 'data' denotes the node value of the binary tree nodes.
Time limit: 1 sec
Think of a recursive solution.
As we can see, before processing any node, the left subtree is processed first, followed by the node, and the right subtree is processed at last. These operations can be defined recursively for each node. The recursive implementation is referred to as a Depth-first search (DFS), as the search tree is deepened as much as possible on each child before going to the next sibling.
The steps are as follows :
O( N ), where ‘N’ is the total number of nodes in the given binary tree.
The recurrence relation is : T( N ) = 2 * T( N / 2 ) + O( 1 ). Apply Master theorem case : c < logba where a = 2 , b = 2 , c = 0. For master theorem http://en.wikipedia.org/wiki/Master_theorem.
Or in simple words, we visit each node of the tree exactly once.
Hence the time complexity is O( N ).
O( N ), where ‘N’ is the total number of nodes in the given binary tree.
The space required is proportional to the tree’s height, which can be equal to the total number of nodes in the tree in the worst case for skewed trees.
Hence the space complexity is O( N ).
All tags
Sort by
Interview problems
Inorder Traversal || Recursion || Java || O(N)
public static List< Integer > getInOrderTraversal(TreeNode root) {
List<Integer> treelist = new ArrayList<>();
inOrderTraversal(root, treelist);
return treelist;
}
public static void inOrderTraversal(TreeNode root, List<Integer> treelist){
if(root == null){
return;
}
inOrderTraversal(root.left, treelist);
treelist.add(root.data);
inOrderTraversal(root.right, treelist);
}
Interview problems
Easy C++ Solution || Inorder Traversal
void inOrder(vector<int>&ans , TreeNode*root){
if(root == nullptr){
return ;
}
inOrder(ans ,root->left);
ans.push_back(root->data);
inOrder(ans ,root->right);
}
vector<int> getInOrderTraversal(TreeNode *root)
{
// Write your code here.
vector<int>ans;
inOrder(ans , root);
return ans;
}
Interview problems
C++ Easy Solution 🔥
/*
Following is Binary Tree Node structure:
class TreeNode
{
public:
int data;
TreeNode *left, *right;
TreeNode() : data(0), left(NULL), right(NULL) {}
TreeNode(int x) : data(x), left(NULL), right(NULL) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : data(x), left(left), right(right) {}
};
*/
void inOrder(TreeNode* root,vector<int> &ans){
if(root==NULL) return;
inOrder(root->left,ans);
ans.push_back(root->data);
inOrder(root->right,ans);
}
vector<int> getInOrderTraversal(TreeNode *root)
{
// Write your code here.
vector<int>result;
inOrder(root,result);
return result;
}Interview problems
C++ solution using recursive approach
/*
Following is Binary Tree Node structure:
class TreeNode
{
public:
int data;
TreeNode *left, *right;
TreeNode() : data(0), left(NULL), right(NULL) {}
TreeNode(int x) : data(x), left(NULL), right(NULL) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : data(x), left(left), right(right) {}
};
*/
void inorder(TreeNode *root ,vector<int>&v)
{
if(root==NULL) return;
inorder(root->left,v);
v.push_back(root->data);
inorder(root->right,v);
}
vector<int> getInOrderTraversal(TreeNode *root)
{
vector<int>v;
inorder(root,v);
return v;
}
Interview problems
Inorder Traversal Easy CPP Solution 100%
void pre(TreeNode *root , vector<int>&ans){
if(root == NULL) return;
pre(root->left , ans);
ans.push_back(root->data);
pre(root->right, ans);
}
vector<int> getInOrderTraversal(TreeNode *root)
{
// Write your code here.
vector<int> ans ;
pre(root , ans);
return ans ;
}
Interview problems
Java Solution
import java.util.List;
import java.util.ArrayList;
public class Solution {
public static List< Integer > getInOrderTraversal(TreeNode root) {
//Approach: Using Recursion
//TC:O(n)| SC:O(h)
List<Integer> arr =new ArrayList<>();
inordertraversal(root, arr);
return arr;
}
public static void inordertraversal(TreeNode root, List<Integer> arr)
{
if(root==null)
return ;
inordertraversal(root.left, arr);
arr.add(root.data);
inordertraversal(root.right, arr);
}
}
Interview problems
Easy Python Solution
ans=[]
def getInOrderTraversal(root):
if root:
getInOrderTraversal(root.left)
ans.append(root.data)
getInOrderTraversal(root.right)
return(ans)
pass
Interview problems
Striver|Recursion|java
/*
Following is the TreeNode class structure:
public class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode() {
this.data = 0;
this.left = null;
this.right = null;
}
TreeNode(int val) {
this.data = val;
this.left = null;
this.right = null;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.data = val;
this.left = left;
this.right = right;
}
};
*/
import java.util.List;
import java.util.ArrayList;
public class Solution {
public static List< Integer > getInOrderTraversal(TreeNode root) {
// Write your code here.
List<Integer> arr =new ArrayList<>();
inorder(root,arr);
return arr;
}
public static void inorder(TreeNode root, List<Integer> arr)
{
if(root == null)
{
return;
}
//left root right
inorder(root.left,arr);
arr.add(root.data);
inorder(root.right,arr);
}
}
Interview problems
O(n) C++ Iterative inOrder traversal of binary tree solution in c++
https://github.com/yashswag22/Striver-A-to-Z-DSA-sheet all solution available in organized way.
vector<int> getInOrderTraversal(TreeNode *root){
vector<int>ans;
if(root == NULL) return ans;
stack<TreeNode*>s;
while(root!= nullptr || !s.empty())
{
if(root == NULL && !s.empty()) {
ans.push_back(s.top()->data);
root = s.top()->right;
s.pop();
}
else{
s.push(root);
root = root -> left;
}
}
return ans;
}Interview problems
Easy for C++
Time complexity O(n)
Space Complexity O(n)
