Tree

Tree

Traversal:

Pre-order traversal

public void preorder(TreeNode root) {
    if (root == null) {
        return;
    }
    // process the node
    // ...
    preorder(root.left);
    preorder(root.right);
}

public List<Integer> preorderTraverse(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  if (root == null) {
     return result;
  }
  Stack<TreeNode> stack = new Stack<>();
  stack.push(root);
  while (!stack.isEmpty()) {
     TreeNode curNode = stack.pop();
     result.add(curNode.val);
     if (curNode.right != null) {
        stack.push(curNode.right);
     }
     if (curNode.left != null) {
        stack.push(curNode.left);
     }
  }
  return result;
}

In-order traversal

public void inorder(TreeNode root) {
    if (root == null) {
        return;
    }
    inorder(root.left);
    // process the node
    // ...
    inorder(root.right);
}


public List<Integer> inorderTraverse(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null) { 
        return list;
    }
    TreeNode curNode = root;
    Stack<TreeNode> stack = new Stack<>();
    while(curNode != null || !stack.empty()){
        while(curNode != null){
            stack.push(curNode);
            curNode = curNode.left;
        }
        curNode = stack.pop();
        list.add(curNode.val);
        curNode = curNode.right;

    }
    return list;
}

Post-order traversal

public void postorder(TreeNode root) {
    if (root == null) {
        return;
    }
    postorder(root.left);
    postorder(root.right);
    // process the node
    // ...
}

public List<Integer> postorderTraverse(TreeNode root) {
    List<Integer> result = new LinkedList<>();
    if (root == null) {
        return result;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode curNode = stack.pop();
        //diff from prorder, insert the node from the first
        result.add(0, curNode.val);
        //diff from preorder, add left first then right
        if (curNode.left != null) {
           stack.push(curNode.left);
        }
        if (curNode.right != null) {
            stack.push(curNode.right);
        }
    }
    return result;
}

Level-order traversal (BFS)

public void levelorder(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            // process the node
            // ...
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        //count depth if need
    }
}

Zigzag traversal

public void zigzag(TreeNode root) {
    if (root == null) {
        return;
    }
    //Doulbe ended queue
    Deque<TreeNode> deque = new ArrayDeque<>();
    deque.offerFirst(root);
    boolean leftToRight = true;
    while (!deque.isEmpty()) {
        int size = deque.size();
        for (int i = 0; i < size; i++) {
            if (leftToRight) {
                TreeNode node = deque.pollFirst();
                // process the node
                // ...
                if (node.left != null) {
                    deque.offerLast(node.left);
                }
                if (node.right != null) {
                    deque.offerLast(node.right);
                }
            } else {
                TreeNode node = deque.pollLast();
                // process the node
                // ...
                if (node.right != null) {
                    deque.offerFirst(node.right);
                }
                if (node.left != null) {
                    deque.offerFirst(node.left);
                }
            }
        }
        leftToRight = !leftToRight;
    }
}

Search:

Depth-first search (DFS)

Finding the minimum/maximum value in a binary search tree (BST)

public int findMin(TreeNode root) {
    while (root.left != null) {
        root = root.left;
    }
    return root.val;
}

public int findMax(TreeNode root) {
    while (root.right != null) {
        root = root.right;
    }
    return root.val;
}



#### Finding the kth smallest/largest element in a BST

```java
public int kthSmallest(TreeNode root, int k) {
    List<Integer> inorder = new ArrayList<>();
    inorderTraversal(root, inorder);
    return inorder.get(k - 1);
}

private void inorderTraversal(TreeNode root, List<Integer> list) {
    if (root == null) {
        return;
    }
    inorderTraversal(root.left, list);
    list.add(root.val);
    inorderTraversal(root.right, list);
}

Checking if two trees are identical or not

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p == null || q == null) {
        return false;
    }
    if (p.val != q.val) {
        return false;
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Find all ancestors for a node

List<TreeNode> ancestors = new ArrayList<>();
public boolean findAllAncestors(TreeNode root, TreeNode target) {
        if (root == null) return false;
        if (root == target) return true;
        boolean left = findAncestors(root.left, target);
        boolean right = findAncestors(root.right, target);
        if (left || right) {
            ancestors.add(root);
        }
        return left || right;
    }

Find items in BST

void BST(TreeNode root, int target) {
    if (root.val == target)
        //find the item
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

Finding the diameter of a binary tree (the length of the longest path between any two nodes)

private int maxDiameter = 0;

public int diameterOfBinaryTree(TreeNode root) {
    maxDepth(root);
    return maxDiameter;
}

private int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
    return Math.max(leftDepth, rightDepth) + 1;
}

Checking if a given tree is balanced or not (height-balanced or weight-balanced)

public boolean isBalanced(TreeNode root) {
    if (root == null) {
        return true;
    }
    return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}

private int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

Calculating the sum of all nodes in a binary tree:

public int sumOfNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return root.val + sumOfNodes(root.left) + sumOfNodes(root.right);
}

Calculating the height of a binary tree:

public int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftHeight = getHeight(root.left);
    int rightHeight = getHeight(root.right);
    return Math.max(leftHeight, rightHeight) + 1;
}

Breadth-first search (BFS)

Finding the shortest path between two nodes

public int shortestPath(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || p == null || q == null) {
        return -1;
    }
    
    Queue<TreeNode> queue = new LinkedList<>();
    Map<TreeNode, TreeNode> parentMap = new HashMap<>();
    queue.offer(root);
    parentMap.put(root, null);
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode curr = queue.poll();
            if (curr == p || curr == q) {
                return getPathLength(parentMap, curr, p, q);
            }
            if (curr.left != null) {
                queue.offer(curr.left);
                parentMap.put(curr.left, curr);
            }
            if (curr.right != null) {
                queue.offer(curr.right);
                parentMap.put(curr.right, curr);
            }
        }
    }
    
    return -1;
}

private int getPathLength(Map<TreeNode, TreeNode> parentMap, TreeNode node, TreeNode p, TreeNode q) {
    Set<TreeNode> visited = new HashSet<>();
    int pathLength = 0;
    
    while (node != null && !visited.contains(node)) {
        visited.add(node);
        pathLength++;
        node = parentMap.get(node);
    }
    
    node = p;
    visited.clear();
    while (node != null && !visited.contains(node)) {
        visited.add(node);
        pathLength++;
        node = parentMap.get(node);
        if (node == q) {
            return pathLength;
        }
    }
    
    node = q;
    visited.clear();
    while (node != null && !visited.contains(node)) {
        visited.add(node);
        pathLength++;
        node = parentMap.get(node);
        if (node == p) {
            return pathLength;
        }
    }
    
    return -1;
}

Counting the number of nodes at a given level

public int countNodesAtLevel(TreeNode root, int level) {
    if (root == null || level < 0) {
        return 0;
    }
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int currLevel = 0;
    
    while (!queue.isEmpty() && currLevel < level) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode curr = queue.poll();
            if (curr.left != null) {
                queue.offer(curr.left);
            }
            if (curr.right != null) {
                queue.offer(curr.right);
            }
        }
        currLevel++;
    }
    
    return queue.size();
}

Finding the depth/height of a node in a binary tree

public int findDepth(TreeNode root, TreeNode node) {
    if (root == null || node == null) {
        return 0;
    }
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int depth = 0;
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        
        for (int i = 0; i < size; i++) {
            TreeNode curr = queue.poll();
            
            if (curr == node) {
                return depth;
            }
            
            if (curr.left != null) {
                queue.offer(curr.left);
            }
            
            if (curr.right != null) {
                queue.offer(curr.right);
            }
        }
        
        depth++;
    }
    
    return -1; // node not found
}

Checking if a binary tree is a complete binary tree

public boolean isCompleteTree(TreeNode root) {
    if (root == null) {
        return true;
    }
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean isEnd = false;
    
    while (!queue.isEmpty()) {
        TreeNode curr = queue.poll();
        
        if (curr == null) {
            isEnd = true;
        } else {
            if (isEnd) {
                return false;
            }
            
            queue.offer(curr.left);
            queue.offer(curr.right);
        }
    }
    
    return true;
}

Finding the minimum depth of a binary tree

public int findMinDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int depth = 1;
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        
        for (int i = 0; i < size; i++) {
            TreeNode curr = queue.poll();
            
            if (curr.left == null && curr.right == null) {
                return depth;
            }
            
            if (curr.left != null) {
                queue.offer(curr.left);
            }
            
            if (curr.right != null) {
                queue.offer(curr.right);
            }
        }
        
        depth++;
    }
    
    return depth;
}

Construction:

Build tree from pre-order and in-order traversal

public TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> inorderMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    return buildTree(preorder, inorderMap, 0, preorder.length - 1, 0, inorder.length - 1);
}

private TreeNode buildTree(int[] preorder, Map<Integer, Integer> inorderMap, int preStart, int preEnd, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd) {
        return null;
    }
    int rootVal = preorder[preStart];
    int rootIndex = inorderMap.get(rootVal);
    int leftSize = rootIndex - inStart;
    TreeNode root = new TreeNode(rootVal);
    root.left = buildTree(preorder, inorderMap, preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
    root.right = buildTree(preorder, inorderMap, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);
    return root;
}

Build tree from post-order and in-order traversal

public TreeNode buildTree(int[] inorder, int[] postorder) {
    Map<Integer, Integer> inorderMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    return buildTree(postorder, inorderMap, postorder.length - 1, 0, inorder.length - 1);
}

private TreeNode buildTree(int[] postorder, Map<Integer, Integer> inorderMap, int postEnd, int inStart, int inEnd) {
    if (inStart > inEnd) {
        return null;
    }
    int rootVal = postorder[postEnd];
    int rootIndex = inorderMap.get(rootVal);
    int rightSize = inEnd - rootIndex;
    TreeNode root = new TreeNode(rootVal);
    root.right = buildTree(postorder, inorderMap, postEnd - 1, rootIndex + 1, inEnd);
    root.left = buildTree(postorder, inorderMap, postEnd - rightSize - 1, inStart, rootIndex - 1);
    return root;
}

Build tree from level-order traversal

public TreeNode buildTree(int[] levelorder) {
    if (levelorder == null || levelorder.length == 0) {
        return null;
    }
    TreeNode root = new TreeNode(levelorder[0]);
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int i = 1;
    while (i < levelorder.length) {
        TreeNode curr = queue.poll();
        int leftVal = levelorder[i];
        if (leftVal != -1) {
            TreeNode left = new TreeNode(leftVal);
            curr.left = left;
            queue.offer(left);
        }
        i++;
        if (i >= levelorder.length) {
            break;
        }
        int rightVal = levelorder[i];
        if (rightVal != -1) {
            TreeNode right = new TreeNode(rightVal);
            curr.right = right;
            queue.offer(right);
        }
        i++;
    }
    return root;
}

Convert binary tree to linked list

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class LinkedListNode {
    int val;
    LinkedListNode next;

    LinkedListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public LinkedListNode convertBinaryTreeToLinkedList(TreeNode root) {
    if (root == null) {
        return null;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    LinkedListNode dummyHead = new LinkedListNode(0);
    LinkedListNode curr = dummyHead;

    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();

            curr.next = new LinkedListNode(node.val);
            curr = curr.next;

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    return dummyHead.next;
}

Convert binary tree to doubly linked list

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class DoublyLinkedListNode {
    int val;
    DoublyLinkedListNode prev;
    DoublyLinkedListNode next;

    DoublyLinkedListNode(int val) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

public DoublyLinkedListNode convertBinaryTreeToDoublyLinkedList(TreeNode root) {
    if (root == null) {
        return null;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    DoublyLinkedListNode dummyHead = new DoublyLinkedListNode(0);
    DoublyLinkedListNode curr = dummyHead;

    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();

            curr.next = new DoublyLinkedListNode(node.val);
            curr.next.prev = curr;
            curr = curr.next;

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    return dummyHead.next;
}

Modification:

Invert binary tree

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;
}

Mirror binary tree

public TreeNode mirrorTree(TreeNode root) {
    if (root == null) return null;
    TreeNode left = mirrorTree(root.left);
    TreeNode right = mirrorTree(root.right);
    root.left = right;
    root.right = left;
    return root;
}

Flatten binary tree

public void flatten(TreeNode root) {
    if (root == null) return;
    flatten(root.left);
    flatten(root.right);
    TreeNode left = root.left;
    TreeNode right = root.right;
    root.left = null;
    root.right = left;
    TreeNode curr = root;
    while (curr.right != null) {
        curr = curr.right;
    }
    curr.right = right;
}

Trim binary search tree

public TreeNode trimBST(TreeNode root, int low, int high) {
    if (root == null) return null;
    if (root.val < low) return trimBST(root.right, low, high);
    if (root.val > high) return trimBST(root.left, low, high);
    root.left = trimBST(root.left, low, high);
    root.right = trimBST(root.right, low, high);
    return root;
}

Delete node from binary search tree

public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        if (root.left == null && root.right == null) {
            root = null;
        } else if (root.right != null) {
            root.val = successor(root);
            root.right = deleteNode(root.right, root.val);
        } else {
            root.val = predecessor(root);
            root.left = deleteNode(root.left, root.val);
        }
    }
    return root;
}

private int successor(TreeNode root) {
    root = root.right;
    while (root.left != null) {
        root = root.left;
    }
    return root.val;
}

private int predecessor(TreeNode root) {
    root = root.left;
    while (root.right != null) {
        root = root.right;
    }
    return root.val;
}

Validation:

Checking if a given binary tree is a BST

public boolean isValidBST(TreeNode root) {
    return isValidBST(root, null, null);
}

private boolean isValidBST(TreeNode root, Integer min, Integer max) {
    if (root == null) {
        return true;
    }
    if ((min != null && root.val <= min) || (max != null && root.val >= max)) {
        return false;
    }
    return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}

Validate balanced binary tree

public boolean isBalanced(TreeNode root) {
    if (root == null) {
        return true;
    }
    int leftHeight = getHeight(root.left);
    int rightHeight = getHeight(root.right);
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return false;
    }
    return isBalanced(root.left) && isBalanced(root.right);
}

private int getHeight(TreeNode node) {
    if (node == null) {
        return 0;
    }
    return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}

Miscellaneous:

Finding the depth of a tree

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
}

Minimum depth of binary tree

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    if (root.left == null) {
        return minDepth(root.right) + 1;
    }
    if (root.right == null) {
        return minDepth(root.left) + 1;
    }
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

Maximum path sum of binary tree

class Solution {
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    private int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        int currSum = node.val + leftGain + rightGain;

        maxSum = Math.max(maxSum, currSum);

        return node.val + Math.max(leftGain, rightGain);
    }
}

Count complete tree nodes

public int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftDepth = getDepth(root.left);
    int rightDepth = getDepth(root.right);
    if (leftDepth == rightDepth) {
        return (1 << leftDepth) + countNodes(root.right);
    } else {
        return (1 << rightDepth) + countNodes(root.left);
    }
}

private int getDepth(TreeNode node) {
    int depth = 0;
    while (node != null) {
        depth++;
        node = node.left;
    }
    return depth;
}

Serialize and deserialize binary tree

public class Codec {
    private static final String SEPARATOR = ",";
    private static final String NULL_NODE = "null";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }

    private void serializeHelper(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(NULL_NODE).append(SEPARATOR);
        } else {
            sb.append(root.val).append(SEPARATOR);
            serializeHelper(root.left, sb);
            serializeHelper(root.right, sb);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(SEPARATOR)));
        return deserializeHelper(nodes);
    }

    private TreeNode deserializeHelper(Queue<String> nodes) {
        String node = nodes.poll();
        if (node.equals(NULL_NODE)) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(node));
        root.left = deserializeHelper(nodes);
        root.right = deserializeHelper(nodes);
        return root;
    }
}

Lowest common ancestor of a binary tree

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left == null) return right;
    if (right == null) return left;
    return root;
}

Lowest common ancestor of BST

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
        return null;
    }
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    } else if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    } else {
        return root;
    }
}

Finding the shortest path between two nodes

DFS solution

import java.util.*;

class TreeNode {
    int val;
    List<TreeNode> children;

    TreeNode(int val) {
        this.val = val;
        this.children = new ArrayList<>();
    }
}

public class ShortestPathInTree {

    public static List<Integer> findShortestPathDFS(TreeNode root, int node1, int node2) {
        List<Integer> path1 = new ArrayList<>();
        List<Integer> path2 = new ArrayList<>();

        findPath(root, node1, path1);
        findPath(root, node2, path2);

        int i;
        for (i = 0; i < path1.size() && i < path2.size(); i++) {
            if (!path1.get(i).equals(path2.get(i))) {
                break;
            }
        }

        List<Integer> shortestPath = new ArrayList<>();
        for (int j = path1.size() - 1; j >= i; j--) {
            shortestPath.add(path1.get(j));
        }
        for (int j = i; j < path2.size(); j++) {
            shortestPath.add(path2.get(j));
        }

        return shortestPath;
    }

    private static boolean findPath(TreeNode root, int target, List<Integer> path) {
        if (root == null) {
            return false;
        }

        path.add(root.val);

        if (root.val == target) {
            return true;
        }

        for (TreeNode child : root.children) {
            if (findPath(child, target, path)) {
                return true;
            }
        }

        path.remove(path.size() - 1);
        return false;
    }
}

BFS solution

import java.util.*;

class TreeNode {
    int val;
    List<TreeNode> children;

    TreeNode(int val) {
        this.val = val;
        this.children = new ArrayList<>();
    }
}

public class ShortestPathInTree {

    public static List<Integer> findShortestPathBFS(TreeNode root, int node1, int node2) {
        Map<Integer, TreeNode> parentMap = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        parentMap.put(root.val, null);

        while (!queue.isEmpty()) {
            TreeNode currentNode = queue.poll();

            if (currentNode.val == node1 || currentNode.val == node2) {
                break;
            }

            for (TreeNode child : currentNode.children) {
                if (!parentMap.containsKey(child.val)) {
                    parentMap.put(child.val, currentNode);
                    queue.offer(child);
                }
            }
        }

        List<Integer> path1 = new ArrayList<>();
        List<Integer> path2 = new ArrayList<>();

        for (int node = node1; node != 0; node = parentMap.get(node).val) {
            path1.add(node);
        }
        for (int node = node2; node != 0; node = parentMap.get(node).val) {
            path2.add(node);
        }

        int i;
        for (i = path1.size() - 1, j = path2.size() - 1; i >= 0 && j >= 0; i--, j--) {
            if (!path1.get(i).equals(path2.get(j))) {
                break;
            }
        }

        List<Integer> shortestPath = new ArrayList<>();
        for (int j = 0; j <= i; j++) {
            shortestPath.add(path1.get(j));
        }
        for (int j = j - 1; j >= 0; j--) {
            shortestPath.add(path2.get(j));
        }

        return shortestPath;
    }
}