Master Linked Lists, Trees, Recursion & Backtracking with Java

Introduction

Welcome to Part 4 of the Top 50 Coding Interview Questions for QA/SDET series.

So far, we've covered:

Part 1: Strings and Arrays
Part 2: HashMaps, Stacks, Queues, and Collection-based problems
Part 3: Two Pointers, Binary Search, Sliding Window, Greedy Algorithms, and Dynamic Programming

In this part, we'll focus on one of the most important areas of technical interviews—Linked Lists, Trees, Recursion, and Backtracking.

Although QA Automation Engineers may not work with these data structures daily, companies such as Amazon, Microsoft, Google, Walmart, ServiceNow, Oracle, Salesforce, and Adobe frequently include these questions to evaluate your understanding of algorithms, recursion, and memory management.

By the end of this article, you'll understand:

Linked List operations
Fast & Slow Pointer technique
Tree Traversals
Binary Tree recursion
Backtracking
Recursive problem solving

Let's begin.

Question 31: Reverse a Linked List

Problem Statement

Reverse a singly linked list.

Example

Input

1 → 2 → 3 → 4 → 5

Output

5 → 4 → 3 → 2 → 1

Why Interviewers Ask This

This problem tests:

Pointer manipulation
Memory understanding
Iterative vs Recursive approaches

Approach

Maintain three pointers:

Previous
Current
Next

Reverse one link at a time.

Java Solution

class ListNode{
    int data;
    ListNode next;

    ListNode(int data){
        this.data=data;
    }
}

public class ReverseLinkedList {

    public static ListNode reverse(ListNode head){

        ListNode prev=null;
        ListNode current=head;

        while(current!=null){

            ListNode next=current.next;

            current.next=prev;

            prev=current;
            current=next;
        }

        return prev;
    }
}

Dry Run

Original

1 → 2 → 3

Step 1

1 ← 2 → 3

Step 2

1 ← 2 ← 3

Final

3 → 2 → 1

Complexity

Time

O(n)

Space

O(1)

Follow-up

Reverse recursively.
Reverse every K nodes.
Reverse between positions M and N.

Question 32: Detect Cycle in a Linked List

Problem Statement

Determine whether a linked list contains a cycle.

Approach

Use Floyd's Cycle Detection Algorithm (Fast & Slow Pointer).

Slow moves one step.
Fast moves two steps.
If they meet, a cycle exists.

Java Solution

public class DetectCycle {

    public static boolean hasCycle(ListNode head){

        ListNode slow=head;
        ListNode fast=head;

        while(fast!=null && fast.next!=null){

            slow=slow.next;
            fast=fast.next.next;

            if(slow==fast)
                return true;
        }

        return false;
    }
}

Complexity

Time

O(n)

Space

O(1)

Interview Tip

Be prepared to explain why the fast and slow pointers eventually meet when a cycle exists.

Question 33: Merge Two Sorted Linked Lists

Problem Statement

Merge two sorted linked lists into a single sorted linked list.

Example

1 → 3 → 5

2 → 4 → 6

Output

1 → 2 → 3 → 4 → 5 → 6

Java Solution

public class MergeLists {

    public static ListNode merge(ListNode l1,ListNode l2){

        ListNode dummy=new ListNode(0);

        ListNode current=dummy;

        while(l1!=null && l2!=null){

            if(l1.data<l2.data){

                current.next=l1;
                l1=l1.next;

            }else{

                current.next=l2;
                l2=l2.next;
            }

            current=current.next;
        }

        if(l1!=null)
            current.next=l1;

        if(l2!=null)
            current.next=l2;

        return dummy.next;
    }
}

Complexity

Time

O(n+m)

Space

O(1)

Question 34: Find the Middle of a Linked List

Problem Statement

Return the middle node of a linked list.

Example

1 → 2 → 3 → 4 → 5

Output

Approach

Use Fast and Slow pointers.

When Fast reaches the end,

Slow points to the middle.

Java Solution

public class MiddleNode {

    public static ListNode middle(ListNode head){

        ListNode slow=head;
        ListNode fast=head;

        while(fast!=null && fast.next!=null){

            slow=slow.next;
            fast=fast.next.next;
        }

        return slow;
    }
}

Complexity

Time

O(n)

Space

O(1)

Question 35: Binary Tree Inorder Traversal

Problem Statement

Perform an inorder traversal of a binary tree.

Traversal order:

Left → Root → Right

Tree Example

Output

2 5 7 10 20

Java Solution

class TreeNode{

    int data;
    TreeNode left,right;

    TreeNode(int data){
        this.data=data;
    }
}

public class InorderTraversal {

    static void inorder(TreeNode root){

        if(root==null)
            return;

        inorder(root.left);

        System.out.print(root.data+" ");

        inorder(root.right);
    }
}

Complexity

Time

O(n)

Space

O(h)

where h is the height of the tree.

Question 36: Maximum Depth of a Binary Tree

Problem Statement

Find the height (maximum depth) of a binary tree.

Recursive Idea

Height of tree

1 + max(leftHeight,rightHeight)

Java Solution

public class MaxDepth {

    static int depth(TreeNode root){

        if(root==null)
            return 0;

        return 1+Math.max(depth(root.left),
                          depth(root.right));
    }
}

Complexity

Time

O(n)

Space

O(h)

Common Mistake

Confusing tree height with the number of edges instead of the number of nodes.

Question 37: Lowest Common Ancestor (Binary Search Tree)

Problem Statement

Find the Lowest Common Ancestor (LCA) of two nodes in a Binary Search Tree.

Example

LCA of

5 and 15

Output

Java Solution

public class LowestCommonAncestor {

    static TreeNode lca(TreeNode root,int p,int q){

        while(root!=null){

            if(p<root.data && q<root.data)
                root=root.left;

            else if(p>root.data && q>root.data)
                root=root.right;

            else
                return root;
        }

        return null;
    }
}

Complexity

Time

O(h)

Space

O(1)

Question 38: Fibonacci Using Recursion and Dynamic Programming

Problem Statement

Find the nth Fibonacci number.

Example

n=7

Output

Recursive Solution

public class Fibonacci{

    static int fib(int n){

        if(n<=1)
            return n;

        return fib(n-1)+fib(n-2);
    }
}

Optimized Dynamic Programming Solution

public class FibonacciDP{

    static int fib(int n){

        if(n<=1)
            return n;

        int prev=0;
        int current=1;

        for(int i=2;i<=n;i++){

            int next=prev+current;

            prev=current;
            current=next;
        }

        return current;
    }
}

Complexity

Recursive

Time

O(2ⁿ)

Space

O(n)

Dynamic Programming

Time

O(n)

Space

O(1)

Interview Tip

Always mention why recursion becomes inefficient due to repeated calculations and how dynamic programming eliminates this redundancy.

Question 39: Generate All Permutations of a String

Problem Statement

Generate all possible permutations of a string.

Input

ABC

Output

ABC
ACB
BAC
BCA
CAB
CBA

Approach

Use Backtracking.

Swap characters.

Recursively solve.

Backtrack by swapping again.

Java Solution

public class Permutations {

    static void permute(char[] arr,int index){

        if(index==arr.length){

            System.out.println(String.valueOf(arr));
            return;
        }

        for(int i=index;i<arr.length;i++){

            char temp=arr[index];
            arr[index]=arr[i];
            arr[i]=temp;

            permute(arr,index+1);

            temp=arr[index];
            arr[index]=arr[i];
            arr[i]=temp;
        }
    }

    public static void main(String[] args){

        permute("ABC".toCharArray(),0);
    }
}

Complexity

Time

O(n!)

Space

O(n)

Interview Follow-up

Generate unique permutations when duplicates exist.
Count permutations instead of printing them.

Question 40: Generate Valid Parentheses

Problem Statement

Generate all valid combinations of parentheses.

Input

n = 3

Output

((()))
(()())
(())()
()(())
()()()

Approach

Use Backtracking.

Rules:

Opening brackets ≤ n.
Closing brackets ≤ Opening brackets.

Java Solution

public class GenerateParentheses {

    static void generate(String current,
                         int open,
                         int close,
                         int n){

        if(current.length()==2*n){

            System.out.println(current);
            return;
        }

        if(open<n)
            generate(current+"(",
                    open+1,
                    close,
                    n);

        if(close<open)
            generate(current+")",
                    open,
                    close+1,
                    n);
    }

    public static void main(String[] args){

        generate("",0,0,3);
    }
}

Complexity

Time

O(4ⁿ/√n)

Space

O(n)

Coding Patterns Covered in Part 4

Pattern	Questions
Linked List	31–34
Fast & Slow Pointer	32, 34
Tree Traversal	35
Tree Recursion	36
Binary Search Tree	37
Dynamic Programming	38
Recursion	38
Backtracking	39, 40

Common Interview Tips

These questions often distinguish average candidates from strong ones because they require both algorithmic thinking and a solid understanding of data structures.

When solving these problems:

Explain your approach before writing code.
Draw the linked list or tree structure if possible.
Clearly describe the base case for recursive solutions.
Discuss iterative and recursive alternatives where applicable.
Analyze both time and space complexity.

Interviewers are often more interested in your reasoning process than your ability to memorize solutions.

What's Next?

In Part 5, we'll complete this series with ten advanced interview questions that are frequently asked in senior QA/SDET interviews, including:

LRU Cache
Implement Min Stack
Top K Frequent Elements
Kth Largest Element
Trie (Prefix Tree)
Word Search
Number of Islands
Longest Consecutive Sequence
Meeting Rooms
Alien Dictionary (Graph-based problem)

These questions introduce advanced data structures and graph algorithms that commonly appear in interviews for senior automation engineers and SDETs at leading product-based companies.

Playwright Tutorial

Java Tutorial

Selenium Tutorial

Rest Assured Tutorial

SQL Tutorial

Git Tutorial

CI / CD Tutorial

Interview Questions

Top 50 Coding Interview Questions for QA/SDET – Part 4 (Questions 31–40)

Master Linked Lists, Trees, Recursion & Backtracking with Java

Introduction

Question 31: Reverse a Linked List

Problem Statement

Why Interviewers Ask This

Approach

Java Solution

Dry Run

Complexity

Follow-up

Question 32: Detect Cycle in a Linked List

Problem Statement

Approach

Java Solution

Complexity

Interview Tip

Question 33: Merge Two Sorted Linked Lists

Problem Statement

Java Solution

Complexity

Question 34: Find the Middle of a Linked List

Problem Statement

Approach

Java Solution

Complexity

Question 35: Binary Tree Inorder Traversal

Problem Statement

Tree Example

Java Solution

Complexity

Question 36: Maximum Depth of a Binary Tree

Problem Statement

Recursive Idea

Java Solution

Complexity

Common Mistake

Question 37: Lowest Common Ancestor (Binary Search Tree)

Problem Statement

Example

Java Solution

Complexity

Question 38: Fibonacci Using Recursion and Dynamic Programming

Problem Statement

Recursive Solution

Optimized Dynamic Programming Solution

Complexity

Interview Tip

Question 39: Generate All Permutations of a String

Problem Statement

Approach

Java Solution

Complexity

Interview Follow-up

Question 40: Generate Valid Parentheses

Problem Statement

Approach

Java Solution

Complexity

Coding Patterns Covered in Part 4

Common Interview Tips

What's Next?