Trees and Binary Trees

Now you: read the code, then draw the tree

No walkthrough this time. Draw it on paper first, then check.

TreeNode root = new TreeNode(50);
root.left = new TreeNode(30);
root.right = new TreeNode(70);
root.left.right = new TreeNode(40);

Tip: in the code, read each dot (.) from left to right. root.left.right means: start at root, go to its left, then go to that node's right.

Draw it on paper first. Then build your drawing below and tap Check my tree.

1. Root?
2. Leaves?
3. Parent of R?
4. Sibling of B?
5. Ancestors of S?
6. Depth of L?
7. Height of T?
8. Size? Edges?
9. Is this a binary tree? Why?

Your coding task: build a tree in Java

In Part 3, you read code and drew the tree. Now go the other way: here is the drawing, and you write the code. Finish buildTree in about 5 lines where it says YOUR CODE, using the TreeNode class from Part 3.

The method at is given, so you can check your tree. Read at(root, "LR") as root.left.right: each L means "go left," and each R means "go right." Run it: each printed line must match its comment.

 1class TreeNode {
 2  int data;
 3  TreeNode left;
 4  TreeNode right;
 5
 6  TreeNode(int value) {
 7    data = value;
 8    left = null;
 9    right = null;
10  }
11}
12
13public class Main {
14  // Builds the tree in the picture and returns its root.
15  static TreeNode buildTree() {
16    TreeNode root = new TreeNode(50);
17    // YOUR CODE: put 30, 70, 20, 40, and 80 in their slots.
18    //         50
19    //        /  \
20    //      30    70
21    //     /  \     \
22    //   20    40    80
23
24    return root;
25  }
26
27  // Given (you do not need to change it): follows a path of
28  // L (left) and R (right) from the root, and returns the value
29  // there, or "null" if there is no node.
30  static String at(TreeNode root, String path) {
31    TreeNode current = root;
32    for (int i = 0; i < path.length(); i++) {
33      if (current == null) {
34        return "null";
35      }
36      if (path.charAt(i) == 'L') {
37        current = current.left;
38      } else {
39        current = current.right;
40      }
41    }
42    if (current == null) {
43      return "null";
44    }
45    return "" + current.data;
46  }
47
48  public static void main(String[] args) {
49    TreeNode root = buildTree();
50    System.out.println(at(root, ""));     // expected: 50
51    System.out.println(at(root, "L"));    // expected: 30
52    System.out.println(at(root, "R"));    // expected: 70
53    System.out.println(at(root, "LL"));   // expected: 20
54    System.out.println(at(root, "LR"));   // expected: 40
55    System.out.println(at(root, "RR"));   // expected: 80
56    System.out.println(at(root, "RL"));   // expected: null
57  }
58}

▶ This program runs as is. Try it in the Programiz online compiler: tap Copy, paste it there, and press Run.

 1static TreeNode buildTree() {
 2  TreeNode root = new TreeNode(50);
 3  root.left = new TreeNode(30);
 4  root.right = new TreeNode(70);
 5  root.left.left = new TreeNode(20);
 6  root.left.right = new TreeNode(40);
 7  root.right.right = new TreeNode(80);
 8  return root;
 9}