# Tree

## Tree

### Traversal:

#### Pre-order traversal

```java
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

```java
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

```java
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)

```java
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

```java
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)**

````java
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**

```java
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

```java
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**

```java
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)**

```java
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)**

```java
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:**

```java
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:**

```java
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**

```java
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**

```java
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**

```java
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**

```java
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**

```java
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

```java
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

```java
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

```java
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

```java
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

```java
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

```java
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

```java
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

```java
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

```java
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

```java
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**

```java
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

```java
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

```java
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

```java
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

```java
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

```java
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

```java
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

```java
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

```java
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

```java
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

```java
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;
    }
}

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding.bea.ai/algorithm-general-templates/tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.