Insertion Binary Tree

Question

Hi I was reading insertion of value in Binary Tree but i am finding difficulty understanding recursive traversal of tree using Java. Here is the code:

// Java program to insert element in binary tree 
import java.util.LinkedList; 
import java.util.Queue; 
public class GFG { 

/* A binary tree node has key, pointer to  
left child and a pointer to right child */
static class Node { 
    int key; 
    Node left, right; 

    // constructor 
    Node(int key){ 
        this.key = key; 
        left = null; 
        right = null; 
    } 
} 
static Node root; 
static Node temp = root; 

/* Inorder traversal of a binary tree*/
static void inorder(Node temp) 
{ 
    if (temp == null) 
        return; 

    inorder(temp.left); 
    System.out.print(temp.key+" "); 
    inorder(temp.right); 
} 

/*function to insert element in binary tree */
static void insert(Node temp, int key) 
{ 
    Queue<Node> q = new LinkedList<Node>(); 
    q.add(temp); 

    // Do level order traversal until we find 
    // an empty place.  
    while (!q.isEmpty()) { 
        temp = q.peek(); 
        q.remove(); 

        if (temp.left == null) { 
            temp.left = new Node(key); 
            break; 
        } else
            q.add(temp.left); 

        if (temp.right == null) { 
            temp.right = new Node(key); 
            break; 
        } else
            q.add(temp.right); 
    } 
} 

// Driver code 
public static void main(String args[]) 
{ 
    root = new Node(10); 
    root.left = new Node(11); 
    root.left.left = new Node(7); 
    root.right = new Node(9); 
    root.right.left = new Node(15); 
    root.right.right = new Node(8); 

    System.out.print( "Inorder traversal before insertion:"); 
    inorder(root); 

    int key = 12; 
    insert(root, key); 

    System.out.print("\nInorder traversal after insertion:"); 
    inorder(root); 
} 
}

Can someone explain how this inorder() method works? Acc to me it should never terminate because it will keep on passing null values again and again and that return statement inside if loop will just loop out of loop and not entire method.

Answer 1

inorder is being called recursively.

At any given call of the methods we pass in the tree's left node first, and right node second. These calls would then call the method for the left node, or the right node, however - if the node is null, it returns early. The tree isn't infinite - so at one point a node's left and right node will have to be null, at which point the method returns early and doesn't continue. Hence the recursion is safely broken at some point.

Also if isn't a loop - it's a conditional statement. Calling return within an if returns from the entire method and doesn't just go out of the if statement. What you must've confused it with is break.