Some topics related to data structures and algorithms in binary trees

Recently, I reviewed several key topics related to data structures and algorithms, and this is the first article focusing on binary trees. Let's start by defining the basic structure of a binary tree:

class TreeNode { int val; // value of the node TreeNode left; // left child TreeNode right; // right child }

Binary tree problems can typically be solved using either recursive or iterative approaches. Here are some common operations and their implementations:

1. Find the maximum depth of a binary tree

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

2. Find the minimum depth of a binary tree

public int getMinDepth(TreeNode root) { if (root == null) return 0; return getMin(root); } private int getMin(TreeNode root) { if (root == null) return Integer.MAX_VALUE; if (root.left == null && root.right == null) return 1; return Math.min(getMin(root.left), getMin(root.right)) + 1; }

3. Count the number of nodes in a binary tree

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

4. Count the number of leaf nodes in a binary tree

public int countLeafNodes(TreeNode root) { if (root == null) return 0; if (root.left == null && root.right == null) return 1; return countLeafNodes(root.left) + countLeafNodes(root.right); }

5. Count the number of nodes at level k in a binary tree

public int countNodesAtLevelK(TreeNode root, int k) { if (root == null || k < 1) return 0; if (k == 1) return 1; return countNodesAtLevelK(root.left, k - 1) + countNodesAtLevelK(root.right, k - 1); }

6. Check if a binary tree is balanced

public boolean isBalanced(TreeNode node) { return getDepth(node) != -1; } private int getDepth(TreeNode node) { if (node == null) return 0; int left = getDepth(node.left); int right = getDepth(node.right); if (left == -1 || right == -1 || Math.abs(left - right) > 1) return -1; return Math.max(left, right) + 1; }

7. Check if a binary tree is a complete binary tree

A complete binary tree is one where all levels are completely filled except possibly the last, which is filled from left to right.

public boolean isComplete(TreeNode root) { if (root == null) return false; Queue queue = new LinkedList<>(); queue.add(root); boolean hasNoChild = false; while (!queue.isEmpty()) { TreeNode current = queue.poll(); if (hasNoChild) { if (current.left != null || current.right != null) return false; } else { if (current.left != null && current.right != null) { queue.add(current.left); queue.add(current.right); } else if (current.left != null) { queue.add(current.left); hasNoChild = true; } else if (current.right != null) return false; else hasNoChild = true; } } return true; }

8. Check if two binary trees are identical

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

9. Check if two binary trees are mirror images of each other

public boolean isMirror(TreeNode t1, TreeNode t2) { if (t1 == null && t2 == null) return true; if (t1 == null || t2 == null) return false; return t1.val == t2.val && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left); }

10. Invert a 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; }

11. Find the lowest common ancestor of two nodes

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 && right != null) return root; return left != null ? left : right; }

12. Preorder traversal of a binary tree

Iterative approach:

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

Recursive approach:

public List preorderTraversalRecursive(TreeNode root) { List result = new ArrayList<>(); preorderHelper(root, result); return result; } private void preorderHelper(TreeNode node, List result) { if (node == null) return; result.add(node.val); preorderHelper(node.left, result); preorderHelper(node.right, result); }

13. Inorder traversal of a binary tree

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

14. Postorder traversal of a binary tree

public List postorderTraversal(TreeNode root) { List result = new ArrayList<>(); if (root == null) return result; result.addAll(postorderTraversal(root.left)); result.addAll(postorderTraversal(root.right)); result.add(root.val); return result; }

15. Construct a binary tree from preorder and inorder traversals

public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder.length != inorder.length) return null; return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1); } private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) { if (inStart > inEnd) return null; TreeNode root = new TreeNode(preorder[preStart]); int index = findIndex(inorder, inStart, inEnd, preorder[preStart]); root.left = build(preorder, preStart + 1, preStart + index - inStart, inorder, inStart, index - 1); root.right = build(preorder, preStart + index - inStart + 1, preEnd, inorder, index + 1, inEnd); return root; } private int findIndex(int[] arr, int start, int end, int target) { for (int i = start; i <= end; i++) { if (arr[i] == target) return i; } return -1; }

16. Insert a node into a binary search tree

public TreeNode insertIntoBST(TreeNode root, TreeNode node) { if (root == null) return node; TreeNode current = root; TreeNode parent = null; while (current != null) { parent = current; if (node.val < current.val) current = current.left; else current = current.right; } if (node.val < parent.val) parent.left = node; else parent.right = node; return root; }

17. Find paths in a binary tree that sum to a given value

public void findPaths(TreeNode root, int targetSum) { if (root == null) return; Stack path = new Stack<>(); findPath(root, targetSum, path, 0); } private void findPath(TreeNode node, int targetSum, Stack path, int currentSum) { currentSum += node.val; path.push(node.val); if (node.left == null && node.right == null) { if (currentSum == targetSum) { for (int num : path) System.out.print(num + " "); System.out.println(); } } if (node.left != null) findPath(node.left, targetSum, path, currentSum); if (node.right != null) findPath(node.right, targetSum, path, currentSum); path.pop(); }

18. Search for values within a range in a binary search tree

public List rangeSearch(TreeNode root, int k1, int k2) { List result = new ArrayList<>(); helper(root, k1, k2, result); return result; } private void helper(TreeNode node, int k1, int k2, List result) { if (node == null) return; if (node.val > k1) helper(node.left, k1, k2, result); if (node.val >= k1 && node.val <= k2) result.add(node.val); if (node.val < k2) helper(node.right, k1, k2, result); }

19. Level order traversal of a binary tree

public List> levelOrder(TreeNode root) { List> result = new ArrayList<>(); if (root == null) return result; Queue queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List level = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(level); } return result; }

20. Find the longest distance between any two nodes in a binary tree

The longest path could be in the left subtree, the right subtree, or pass through the root. Using a helper class to track both the maximum depth and the maximum distance:

private static class Result { int maxDistance; int maxDepth; public Result() {} public Result(int maxDistance, int maxDepth) { this.maxDistance = maxDistance; this.maxDepth = maxDepth; } } public int longestPath(TreeNode root) { return getLongestPath(root).maxDistance; } private Result getLongestPath(TreeNode node) { if (node == null) return new Result(0, -1); Result left = getLongestPath(node.left); Result right = getLongestPath(node.right); Result result = new Result(); result.maxDepth = Math.max(left.maxDepth, right.maxDepth) + 1; result.maxDistance = Math.max(left.maxDepth + right.maxDepth, Math.max(left.maxDistance, right.maxDistance)); return result; }

21. Count different binary search trees with n nodes

public int numTrees(int n) { int[] dp = new int[n + 1]; dp[0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { dp[i] += dp[j] * dp[i - j - 1]; } } return dp[n]; }

22. Check if a binary tree is a valid binary search tree (BST)

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

These examples cover a wide range of binary tree problems that are commonly encountered in technical interviews. Understanding these concepts and their implementations will greatly help in solving similar problems efficiently. Whether you're working with recursion, iteration, or tree traversal techniques, having a solid grasp of binary trees is essential for any software engineer or developer.

Phone Stand Amazon

Shenzhen ChengRong Technology Co.,Ltd. , https://www.laptopstandsupplier.com