Unravel › Java concepts › Algorithms and data structures

Learn these first

At a glance

1. 1Node: class TreeNode { int val; TreeNode left, right; }A tree is a reference to its root; empty subtrees are null.
2. 2Depth-first traversals: preorder (node, left, right), inorder (left, node, right), postorder (left, right, node)Inorder on a binary search tree visits the values in sorted order.
3. 3Breadth-first (level order) uses a queue: add the root, then repeatedly poll a node and add its children
4. 4Height: 1 + Math.max(height(left), height(right)) with 0 for nullBinary search tree: values less than the node go left, larger go right, so search, insert and delete are O(height).

• A balanced tree has height about log n, so operations are O(log n); a degenerate tree (inserting sorted data into a plain BST) is a linked list with O(n) operations
• Recursion depth equals the tree height; for very deep trees use an explicit Deque stack
• A node is a heap object with two references, so a tree of n nodes uses n objects

import java.util.*;public class Trees {  static class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } }  static int maxDepth(TreeNode node) {    if (node == null) return 0;    return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));  }  static void inorder(TreeNode node, List<Integer> out) {    if (node == null) return;    inorder(node.left, out);    out.add(node.val);    inorder(node.right, out);  }  static TreeNode insertNode(TreeNode root, int v) {    if (root == null) return new TreeNode(v);    if (v < root.val) root.left = insertNode(root.left, v); else root.right = insertNode(root.right, v);    return root;  }}

1. line 3 uses TreeNode, the core of Trees and tree traversal
2. line 4 uses TreeNode, the core of Trees and tree traversal
3. line 8 uses TreeNode, the core of Trees and tree traversal
4. line 14 uses TreeNode, the core of Trees and tree traversal
5. line 15 uses TreeNode, the core of Trees and tree traversal

How Unravel recognises it

When you paste code, Unravel looks for these signs of trees and tree traversal. Spotting them yourself is a good habit when you read unfamiliar code:

• Types: TreeNode
• Method names you declare: inorder() preorder() postorder() levelOrder() insertNode() height() maxDepth()
• Created with new: TreeNode

Part of a learning path

• Algorithms and data structures · previous: Building your own stack or queue · next: Graphs: BFS and DFS

Related concepts