The task is to find the in-order traversal of a given binary tree.

• Implement a recursive function to perform in-order traversal of the binary tree

• Start from the left subtree, then visit the root, and f...read more

This was simple question , here only had to traverse in inorder in a tree

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 :

1. We create a recursive function inOrderHelper() which takes the root of the tree as an argument.
2. inOrderHelper() :
   • Visit the left subtree of ‘node’ i.e., call inOrderHelper(‘node’ -> left).
   • Visit ‘node’ and if ‘node’ != NULL then add data of node to answer.
   • Visit the right subtree of ‘node’ i.e., call inOrderHelper(‘node’ -> right).

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 ).

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 < log_ba ⁡ where a = 2 , b = 2 , c = 0. For master theorem -----Master_theorem.

Or in simple words, we visit each node of the tree exactly once.

Hence the time complexity is O( N ).

/*

    Time Complexity: O( N )

    Space Complexity: O( N )



    where N is the total number of nodes in the given binary tree.

*/



import java.util.*;

import java.io.*;



public class Solution {



    public static List < Integer > getInOrderTraversal(TreeNode root) {



        // Create answer array to store traversal.

        List < Integer > answer = new ArrayList < Integer > ();



        // Call inOrderHelper function and store preOrder traversal in answer array.

        inOrderHelper(root, answer);



        // Return answer.

        return answer;

    }



    // Helper function.

    public static void inOrderHelper(TreeNode node, List < Integer > answer) {

        // Base case.

        if (node == null) {

            return;

        }



        // Visit left subtree.

        inOrderHelper(node.left, answer);



        // Add data of node to answer.

        answer.add(node.data);



        // Visit right subtree.

        inOrderHelper(node.right, answer);

    }

}

'''

    Time Complexity  : O(N)

    Space Complexity : O(N)



    Where 'N' is the total number of nodes in the binary tree.

'''





def inOrderHelper(root, answer):

    # Base case.

    if root == None:

        return



    # Visit left subtree.

    inOrderHelper(root.left, answer)



    # Add data of node to answer.

    answer.append(root.data)



    # Visit right subtree.

    inOrderHelper(root.right, answer)





def getInOrderTraversal(root):

    # Use answer to store traversal of nodes.

    answer = []



    # Call inOrderHelper function and store inOrder traversal in answer array.

    inOrderHelper(root, answer)



    # Return answer.

    return answer

/*

    Time Complexity: O( N )

    Space Complexity: O( N )



    where ‘N’ is the total number of nodes in the given binary tree.

*/



void inOrderHelper(TreeNode *node, vector &answer)

{

    // Base case.

    if (node == NULL)

    {

        return;

    }



    // Visit left subtree.

    inOrderHelper(node->left, answer);



    // Add data of node to answer.

    answer.push_back(node->data);



    // Visit right subtree.

    inOrderHelper(node->right, answer);

}



vector getInOrderTraversal(TreeNode *root)

{

    // Use answer to store traversal of nodes.

    vector answer;



    // Call inOrderHelper function and store inOrder traversal in answer array.

    inOrderHelper(root, answer);



    // Return answer.

    return answer;

}

To convert the above recursive procedure into an iterative one, we need an explicit stack.

The steps are as follows :

1. Create an empty stack and initialize the current node as root.
2. Run...read more

The idea here is to use Morris traversal for the Inorder traversal of the tree. The idea of Morris's traversal is based on the Threaded Binary Tree.  In this traversal, we will create links to the predecessor back to the current node so that we can trace it back to the top of a binary tree. Here we don’t need to find a predecessor for every node, we will be finding a predecessor of nodes with only a valid left child.

So Finding a predecessor will take O( N ) as time as we will be visiting every edge at most two times and there are only ‘N’ - 1 edges in a binary tree. Here ‘N’ is the total number of nodes in a binary tree.

For more details, please check the Threaded binary tree and Explanation of Morris Method

The steps are as follows :

1. Create a new node, say ‘CURRENT’, and initialize it as ‘ROOT’.
2. Run a loop until ‘CURRENT’ !=NULL and do:
   • If CURRENT -> left = NULL then add data of current to answer and do CURRENT = CURRENT -> right
   • Else In current’s left subtree, make ‘CURRENT’ as of the right child of rightmost node and visit this left child i.e. CURRENT = CURRENT -> left.

O( 1 )

In the worst-case constant space is required.

Hence the space complexity is O( 1 ).

O( N ), where ‘N’ is the total number of nodes in the given binary tree.

In the worst case, we are visiting each node at most twice in Inorder traversal.

Hence the time complexity is O( N ).

/*

    Time Complexity: O( N )

    Space Complexity: O( 1 )



    where N is the total number of nodes in the given binary tree.

*/



import java.util.*;

import java.io.*;



public class Solution {



    public static List < Integer > getInOrderTraversal(TreeNode root) {



        // Create answer array to store traversal.

        List < Integer > answer = new ArrayList < Integer > ();



        // Base case.

        if (root == null) {

            return answer;

        }



        // 'PREDECESSOR' and 'CURRENT' will store predecessor and current nodes, respectively.

        TreeNode current, predecessor;



        // Initialize current node as 'ROOT'.

        current = root;



        // Run a loop until 'CURRENT' != NULL.

        while (current != null) {



            if (current.left == null) {



                // Add current node data to answer.

                answer.add(current.data);



                // Move to right child of current.

                current = current.right;

            } else {



                // Find predecessor of current node.

                predecessor = current.left;

                while (predecessor.right != null && predecessor.right != current) {

                    predecessor = predecessor.right;

                }



                if (predecessor.right == null) {

                    /*

                        Make a link between predecessor and current node

                        so that we have a path to come back to current

                        when we have traversed the whole left subtree.

                    */

                    predecessor.right = current;

                    current = current.left;

                } else {

                    /*

                        If right node of predecessor is not NULL then it

                        means we have traversed the whole left subtree.

                        So we unlink the connection between current and predecessor

                        and move to right node of current.

                    */

                    predecessor.right = null;

                    answer.add(current.data);

                    current = current.right;

                }

            }

        }



        // Return answer.

        return answer;

    }

}

/*

    Time Complexity: O( N )

    Space Complexity: O( 1 )



    where ‘N’ is the total number of nodes in the given binary tree.

*/



// Morris Traversal for inOrder.

vector getInOrderTraversal(TreeNode *root)

{



    // Create answer array to store traversal.

    vector answer;



    // Base case.

    if (root == NULL)

    {

        return answer;

    }



    // 'PREDECESSOR' and 'CURRENT' will store predecessor and current nodes, respectively.

    TreeNode *current, *predecessor;



    // Initialize current node as 'ROOT'.

    current = root;



    // Run a loop until 'CURRENT' != NULL.

    while (current != NULL)

    {

        if (current->left == NULL)

        {

            answer.push_back(current->data);

            current = current->right;

        }

        else

        {



            // Find the rightmost node on the left subtree of current.

            predecessor = current->left;

            while (predecessor->right != NULL && predecessor->right != current)

            {

                predecessor = predecessor->right;

            }



            if (predecessor->right == NULL)

            {

                /*

                    Make a link between predecessor and current node

                    So that we have a path to come back to current

                    When we have traversed the whole left subtree.

                */

                predecessor->right = current;

                current = current->left;

            }

            else

            {

                /*

                    If right node of predecessor is not NULL then it

                    Means we have traversed the whole left subtree.

                    So we unlink the connection between current and predecessor

                    And move to right node of current.

                */

                predecessor->right = NULL;

                answer.push_back(current->data);

                current = current->right;

            }

        }

    }



    return answer;

}

'''

    Time Complexity  : O(N)

    Space Complexity : O(1)



    Where 'N' is the total number of nodes in the binary tree.

'''





def getInOrderTraversal(root):

    # Use answer to store traversal of nodes.

    answer = []



    # Base case.

    if (root == None):

        return answer



    # 'PREDECESSOR' and 'CURRENT' will store predecessor and current nodes, respectively.

    current = None

    predecessor = None



    # Initialize current node as 'ROOT'.

    current = root



    # Run a loop until 'CURRENT' != None.

    while (current != None):

        if (current.left == None):

            answer.append(current.data)

            current = current.right

        else:

            # Find the rightmost node on the left subtree of current.

            predecessor = current.left

            while (predecessor.right != None and predecessor.right != current):

                predecessor = predecessor.right



            if (predecessor.right == None):

                '''

                    Make a link between predecessor and current node

                    So that we have a path to come back to current

                    When we have traversed the whole left subtree.

                '''

                predecessor.right = current

                current = current.left

            else:

                '''

                    If right node of predecessor is not None then it

                    Means we have traversed the whole left subtree.

                    So we unlink the connection between current and predecessor

                    And move to right node of current.

                '''

                predecessor.right = None

                answer.append(current.data)

                current = current.right



    # Return answer.

    return answer