This pattern is based on the Depth First Search (DFS) technique to traverse a tree.

We will be using recursion (or we can also use a stack for the iterative approach) to keep track of all the previous (parent) nodes while traversing. This also means that the space complexity of the algorithm will be O(H), where ‘H’ is the maximum height of the tree.

Algorithms

Inorder iterative traversal

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

Path sum recursive

public boolean hasPath(TreeNode root, int sum) {
    if (root == null)
        return false;

    // if the current node is a leaf and its value is equal to the sum, we've found a path
    if (root.val == sum && root.left == null && root.right == null)
        return true;

    // recursively call to traverse the left and right sub-tree
    // return true if any of the two recursive call return true
    return hasPath(root.left, sum - root.val) || hasPath(root.right, sum - root.val);
}

Path sum iterative traversal

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    if (root == null) return new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    Stack<Integer> values = new Stack<>();
    while (!stack.isEmpty() || root != null) {
        while (root != null) {
            sum -= root.val;
            values.add(root.val);
            stack.add(root);
            root = root.left;
        }

				//is Leaf
        if (sum == 0 && stack.peek().left == null && stack.peek().right == null) {
            result.add(new ArrayList<>(values));
        }

        while (!stack.isEmpty() && stack.peek().right == root) {
            root = stack.pop();
            values.pop();
            sum += root.val;
        }

        root = stack.isEmpty() ? null : stack.peek().right;
    }

    return result;
}

Tree diameter (global variable diameter)

int diameter;

public int findDiameter(TreeNode root) {
    calcHeight(root);
    return diameter;
}

private int calcHeight(TreeNode root) {
    if (root == null) return 0;

    int left = calcHeight(root.left);
    int right = calcHeight(root.right);

    diameter = Math.max(diameter, left + right + 1);

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

Count number of paths (kinda bactracking)

public int pathSum(TreeNode root, int sum) {
    if (root == null) return 0;

    return pathSum(root, sum, new LinkedList<>());
}

private int pathSum(TreeNode root, int sum, List<Integer> currPath) {
    if (root == null) return 0;

    currPath.add(root.val);

    int pathCount = 0, pathSum = 0;
    for (int i = currPath.size() - 1; i >= 0; i--) {
        pathSum += currPath.get(i);
        if (pathSum == sum) {
            pathCount++;
        }
    }

    pathCount += pathSum(root.left, sum, currPath);
    pathCount += pathSum(root.right, sum, currPath);

    currPath.remove(currPath.size() - 1);

    return pathCount;
}

Untitled

https://leetcode.com/articles/count-complete-tree-nodes/

Approach

Most of the case we're using recursive algorithm. Stack or List can be used for keeping path values.

For iterative algorithm stack is suitable for storing nodes.