Tree In Java ☕

Introduction

Welcome, Fellow Code Explorers!

Ever feel like your data is a tangled mess, scattered like socks after laundry day? Well, fear not, because today we're diving headfirst into the wonderful world of trees! No, not the leafy kind that photosynthesize (though those are pretty cool too). We're talking about the data structure kind, which are far more organized and, dare I say, less prone to bird nests.

In this post, we're going to unravel the mysteries of trees, from their roots (pun intended!) to their branches. We'll start with a solid definition and get acquainted with some fancy tree-related lingo. Then, we'll explore how to navigate these digital forests with traversal algorithms – think of it as finding your way without a GPS, but for data. Finally, and this is where the real fun begins, we'll roll up our sleeves and get our hands dirty with the implementation of trees using Java. So, if you've ever wanted to build your own digital arboretum, you're in the right place!

Now, a little heads-up: to truly appreciate the exquisite beauty of our Java implementation, a basic understanding of Java's Object-Oriented Programming (OOP) concepts – like generic classes, interfaces, and abstract classes – will be super helpful. If that last sentence made your eyes glaze over, don't panic! Just drop a comment below, and I might just whip up a "Java OOP for Dummies (Who Want to Conquer Trees)" post.

While I recommend following along section by section for maximum enlightenment (and minimal head-scratching), if you're a busy bee with places to be and code to conquer, feel free to fast-forward straight to the Implementation section. Just promise me you'll come back for the foundational stuff later! And hey, a little pro tip from your friendly neighborhood coder: grab a notebook! Jotting things down can make a world of difference.

For this grand adventure, I've leaned heavily on the wisdom found in "Data Structures and Algorithms in Java™" (a classic!) and received some minor assists from our good friends at GeeksforGeeks.

Your feedback is like sunshine to a programmer's soul, so please, don't be a stranger! Share your thoughts in the comments or follow my Telegram Channel. Let's make this post even better, together!

Definition

💡 Abstract Data Type (ADT) a mathematical model of a data structure that defines a set of operations on the data without specifying how the data is actually stored or implemented. Essentially, it's a blueprint or specification for how a data structure should behave, focusing on the "what" rather than the "how".

Think of a tree in the world of data structures not as something you'd climb for a picnic, but rather as the ultimate organizational chart. It's an abstract data type that loves to store elements in a neat, hierarchical fashion. And just like any good family tree (or corporate ladder), every element has a proud parent called p, except for that one big shot at the very top – the root – who's clearly self-made. Below them, you'll find zero or more children, diligently (or perhaps lazily) waiting their turn.

Formally, we define a tree T as a set of nodes storing elements, where these nodes have a parent-child relationship that satisfies some rather specific (and orderly!) properties:

• If T is feeling non-empty, it proudly features a special node, humorously dubbed the root of T. This root node, much like a self-made entrepreneur, has no parent to report to.
• Every other node n of T has a unique parent node w. And to keep things nice and tidy, every node with parent w is, by definition, a child of w. (No identity crises in our data trees!)

External, internal node and many more

Two nodes that are children of the same parent are siblings. A node v is external or a.k.a leaves If v has no children. A node v is internal if it has one or more children.

• Edge: An edge is a connection between two nodes in a tree. In a rooted tree, edges link parent nodes to child nodes, forming hierarchical relationships.
• Path: A path is a sequence of edges connecting one node to another. The length of the path is measured by the number of edges it contains.

An ordered tree is a type of tree in which the children of each node follow a specific order. This means that the arrangement of child nodes matters, and changing their sequence would result in a different tree structure. E.g. In a binary search tree (BST) (there will be a dedicated post about search tree coming soon.), the left child contains values smaller than the parent, and the right child contains values larger.

Traversal

• Preorder Traversal

  When it comes to a preorder traversal of a tree T, think of it as the ultimate "boss first" policy. The root of T gets all the attention and is visited immediately, soaking in the glory. Only after the root has had its moment in the spotlight do we then (and only then!) recursively traverse the sub-trees rooted at its children. It's like the CEO getting their coffee before anyone else – efficiency, right? You can find its implementation in Java here.

  💡This is the pseudocode representation of the algorithm.
  

 func preorder(p):
        print p + ' ';
        for each child c in children(p) do
            preorder(c);

• Postorder Traversal

  Now, if preorder is the "boss first" type, then postorder traversal is decidedly more... familial. In a postorder traversal, we recursively traverse all the subtrees rooted at the children of the root first. We let the little ones have their fun, run around, and get everything sorted. Only after every single child and grandchild (and great-grandchild!) has been visited do we finally get around to visiting the root. It's like serving dessert to the kids before the parents get their main course.

  You can find its implementation in Java here.

  💡 This is the algorithm pseudocode
  

 func postorder(p):
        for each child c in children(p) do
            postorder(c);
        print p + ' ';

• Breadth-First Tree Traversal BFS

  Now, if preorder is the CEO and postorder is the clean-up crew, then Breadth-First Traversal (Level Order Traversal) is the ultimate party host! This technique is all about being fair and organized. We traverse the tree level by level, making sure everyone at the current depth d gets visited completely before we even think about moving on to the next depth d+1. It's like mingling with all the guests in the living room before you even consider heading to the kitchen.

  And here's the kicker: this isn't some fancy recursive dive into subtrees. Oh no, we're far too systematic for that! Instead, we grab a handy-dandy queue, which ensures a strict FIFO (First-In, First-Out) policy. So, the first node we encounter at a level is the first one we process, making sure no one at the current depth d feels left out. It's democracy, but for data!

  You can find its implementation in Java here.

  

Output: [[5], [12, 13], [7, 14, 2], [17, 23, 27, 3, 8, 11]] or [5, 12, 13, 7, 14, 2, 17, 23, 27, 3, 8, 11]

Explanation:
Level 0: Start with the root → [5]
Level 1: Visit its children → [12, 13]
Level 2: Visit children of 12 and 13 → [7, 14, 2]
Level 3: Visit children of 7, 4 and 12 → [17, 23, 27, 3, 8, 11]

💡 You can change level to depth they can be interchangeable

💡 Pseudocode for Breath First Search or BFS

func breadthfirst():
        Initialize queue Q to contain root();
        while Q not empty do
            p = Q.dequeue();
            print p + ', '; 
            for each child c in children(p) do
                    Q.enqueue(c);

💡 The standard preorder, postorder, and breadth-first traversals that were introduced for general trees can be directly applied to binary trees.

• Inorder Traversal of a Binary Tree

  If preorder is the boss and postorder is the cleanup crew, then inorder traversal is the quintessential "middle child syndrome" algorithm – specifically for binary trees! Informally, you can imagine it as visiting the nodes of T "from left to right," much like reading a perfectly ordered book. For every node p, we first (and meticulously!) traverse all the children in its left subtree. Only after that entire left side has been thoroughly explored do we finally get around to visiting p itself (the parent, the star of the show!). And then, once p has had its moment, we gracefully move on to traverse all the children in its right subtree. It's all about Left, then Parent, then Right – a very polite and sequential visit, indeed.

  You can find its implementation in Java here.

💡 This is the algorithm pseudocode

  func inorder(p):
         if p has a left child lc then:
                 inorder(lc)
         print p + ', ';
         if p has a right child rc then
                 inorder(rc)

Implementing Tree On Java ☕

💡 First let us talk ( write on this case ) about position basically it is an interface that has only one method called getElement() that will return an element that is stored in it. We will implement this interface on the node class.

Why "Position" is Better for Tree Nodes (and Its Catch)

Alright, imagine you're trying to find your favorite snack in a massive, chaotic pantry (that's your tree, by the way). How do you locate that elusive bag of chips?

You might think, "Aha! I'll just give everything an index, like putting numbers on shelves!" Sounds smart, right? Well, in the world of trees, using indexes for nodes is like trying to navigate a dance party with a map that keeps changing.

Here's why indexes in trees are about as reliable as my New Year's resolutions:

• Indexes are unstable: Picture this: you finally find your chips at index 7. But then, someone adds a giant box of cereal at the beginning of the shelf. Suddenly, your chips are now at index 8! Or worse, someone eats your chips (rude!) and removes them. Now index 7 points to a jar of pickles, or nothing at all! In tree-speak, if you remove or move a node, all the other indexes can shift faster than a cat knocking things off a counter. Trying to find a node by its old index? Good luck – you'll likely end up staring at the wrong thing, or worse, an empty spot where your data used to be.
• Indexes are slow to find: Even if your indexes weren't playing musical chairs, finding a specific index in a tree is like trying to find a needle in a haystack by checking every single piece of hay. In the worst case, to find a node at a specific index, you might have to check every single node in the tree. For a large tree, that's what we call O(n) time – basically, it gets agonizingly slow as your tree (or pantry) grows.

This is precisely why we ditch the unreliable index system and embrace the glorious Position! Think of a position as a node's personal, unchangeable GPS coordinate or a permanent, unique "address" that it was born with.

And why is this Position thing so much better?

• Positions are stable: A node's position is like its DNA – it stays the same no matter how many new nodes join the party, how many get kicked out, or if anyone rearranges the furniture. It's that unique ID tag that always points to the exact same node, no questions asked. It's the steadfast friend who never moves!
• Positions are fast to find: Because each node has its own unique, unwavering position, you can go directly to it. No sifting through other nodes, no guessing games. This is what we call O(1) time – meaning it's lightning-fast, taking a constant amount of time regardless of whether your tree has five nodes or five million. It's like having a teleportation device straight to your data!

Now, for the catch (because there's always a catch, isn't there?): While positions are fantastically stable and fast, you actually have to store that unique position for each node if you want to find it later. It's like needing to remember your best friend's specific home address and postcode if you ever want to surprise them with pizza. It's worth it for the reliability, but it does mean a tiny bit more effort on your part to keep track of those precious positions!

To implement position create a Position.java file and add this code inside it.

public interface Position {
    E getElement() throws IllegalStateException;
}

Abstract Tree

The Tree Abstract Data Type

💡 We define a tree ADT using the concept of a position as an abstraction for a node of a tree. An element is stored at each position, and positions satisfy parent-child relationships that define the tree structure. for now consider position as a Node .

• The position object for a tree support the method

  getElement(): Returns the element stored at this position.

• Accessor Methods

  root(): Returns the position of the root of the tree (or null if empty).

  parent(p): Returns the position of the parent of position p (or null if p is the root).

  children(p): Returns an iterable collection containing the children of position p (if any).

  numChildren(p): Returns the number of children of position p.

• Query Method

  isInternal(p): Returns true if position p has at least one child.

  isExternal(p): Returns true if position p does not have any children.

  isRoot(p): Returns true if position p is the root of the tree.

• Other General Tree Methods

  size(): Returns the number of positions (and hence elements) that are contained in the tree.

  isEmpty(): Returns true if the tree does not contain any positions (and thus no elements).

  iterator(): Returns an iterator for all elements in the tree (so that the tree itself is Iterable).

  positions(): Returns an iterable collection of all positions of the tree.

💡 If an invalid position is sent as a parameter to any method of a tree, then an IllegalArgumentException is thrown.

We'll start by defining the Tree interface to list the basic functions required for any tree. Create the Tree.java file and add this code:

import java.util.Iterator;

public interface Tree<E> extends Iterable<E> {
    Position<E> root();

    Position<E> parent(Position<E> p) throws IllegalArgumentException;

    Iterable<Position<E>> children(Position<E> p) throws IllegalArgumentException;

    int numChildren(Position<E> p) throws IllegalArgumentException;

    boolean isInternal(Position<E> p) throws IllegalArgumentException;

    boolean isExternal(Position<E> p) throws IllegalArgumentException;

    boolean isRoot(Position<E> p) throws IllegalArgumentException;

    int size();

    boolean isEmpty();

    Iterator<E> iterator();

    Iterable<Position<E>> positions();

}

Next, we need an abstract class that will serve as a base for all tree types inheriting from it. Create an AbstractTree.java file and add this code to it.

public abstract class AbstractTree<E> implements Tree<E> { 
    // do something 
}

Next, we will add methods for querying the tree write this code on AbstractTree.java .

@Override
public boolean isEmpty() {
    return size() == 0;
}

@Override
public boolean isExternal(Position<E> p) throws IllegalArgumentException {
    return numChildren(p) == 0;
}

@Override
public boolean isInternal(Position<E> p) throws IllegalArgumentException {
    return numChildren(p) > 0;
}

@Override
public boolean isRoot(Position<E> p) throws IllegalArgumentException {
    return p == root();
}

Some methods like size(), numChildren() and root() are not implemented in this abstract class. Instead, they must be implemented by any concrete class that extends AbstractTree.java.

we add isEmpty() to know if the tree is empty.

Depth and height of a tree

• Depth: The depth of a position p in a tree is the number of edges from the root to that node. It measures how far the p is from the root or the number of ancestors of p, other than p itself.
  • If p is the root, then the depth of p is 0.
  • Otherwise, the depth of p is one plus the depth of the parent of p

Add the following code to calculate the Depth of position p in AbstractTree.java.

public int depth(Position<E> p) {
    if (isRoot(p))
        return 0;
    else
        return 1 + depth(parent(p));
}

• Height: The height of a tree is the longest path from the root to a leaf. A tree with only one position (just the root) has a height of 0.

• Formally, we define the height of a position p in a tree T as follows:

  • If p is a leaf, then the height of p is 0.
  • Otherwise, the height of p is one more than the maximum of the heights ofp’s children.

Add the following code to calculate the Height of a Tree in AbstractTree.java.

public int height(Position<E> p) {
    int h = 0;
    for (Position<E> c : children(p)) {
        h = Math.max(h, 1 + height(c));
    }
    return h;
}

Iterator

To enable traversal and access of tree elements, we need to implement iterator functionality. Add the following code to the AbstractTree.java file.

 private class ElementIterator implements Iterator<E> {
    Iterator<Position<E>> posIterator = positions().iterator();

    @Override
    public boolean hasNext() {
        return posIterator.hasNext();
    }

    @Override
    public E next() {
        return posIterator.next().getElement();
    }

    public void remove() {
        posIterator.remove();
    }

}

@Override
public Iterator<E> iterator() {
    return new ElementIterator();
}

We create an inner class, ElementIterator, which implements the Iterator interface. (The Iterator interface is beyond the scope of this post; comment below if you'd like a dedicated explanation.)

The positions method, inside ElementIterator, lacks an implementation in AbstractTree.java. So, any concrete class inheriting from AbstractTree must provide its own implementation for this method.

Traversing

Time to Code!

Alright, code explorers! We've journeyed through the theoretical forests of tree traversals, understanding the ins and outs of Preorder, Postorder, Inorder, and Breadth-First approaches.

But let's be real, simply knowing about traversals is like having a fantastic recipe without ever stepping into the kitchen. So, in this section, we're finally going to get our hands gloriously dirty with the practical implementation! This is where the rubber meets the road, where those theories transform into actual, runnable Java code. Get ready to turn abstract concepts into concrete lines of Java. It's time to make our trees sing!

• Preorder Traversal

  Add the following code on AbstractTree.java
  

  private void preorderSubtree(Position<E> p, List<Position<E>> snapshot) {
      snapshot.add(p);
      for (Position<E> c : children(p)) {
          preorderSubtree(c, snapshot);
      }
  }
  
  public Iterable<Position<E>> preorder() {
      List<Position<E>> snapshot = new ArrayList<>();
      if (!isEmpty())
          preorderSubtree(root(), snapshot);
      return snapshot;
  }
  

💡 Here an ArrayList implement Iterable interface.

• Postorder Traversal

  Add the following code on AbstractTree.java
  

  private void postorderSubtree(Position<E> p, List<Position<E>> snapshot) {
    for (Position<E> c : children(p)) {
        postorderSubtree(c, snapshot);
    }
    snapshot.add(p);
  }
  
  public Iterable<Position<E>> postorder() {
    List<Position<E>> snapshot = new ArrayList<>();
    if (!isEmpty())
        postorderSubtree(root(), snapshot);
  
    return snapshot;
  }
  

• Breadth-First Tree Traversal BFS

  Add the following code on AbstractTree.java
  

  public Iterable<Position<E>> breadthfirst() {
        List<Position<E>> snapshot = new ArrayList<>();
        if (!isEmpty()) {
            Queue<Position<E>> fring = new LinkedList<>();
            fring.add(root());
            while (fring.size() > 0) {
                Position<E> p = fring.remove();
                snapshot.add(p);
                for (Position<E> c : children(p)) {
                    fring.add(c);
                }
            }
        }
  
        return snapshot;
  }
  

💡 Given that these traversal methods are universally adored by all tree types (they're just that versatile!), we'll be placing their implementation where they belong: directly within our AbstractTree class. Think of it as a one-stop shop for all your tree-walking needs.

import this packages

import java.util.ArrayList;
import java.util.List;

Binary Tree

💡 Let's talk about the binary tree – it's like the slightly more strict parent in the data structure family. It's still a hierarchical structure, but each node has a very clear rule: "You get at most two children, and they must be designated as either the 'left child' or the 'right child.'" No middle children, no more than two, thank you very much!

Now, within the binary tree world, we have our overachievers: the proper binary tree (also sometimes called a full binary tree). These are the nodes that really commit to the family plan. Every node in a proper binary tree has either zero children (the happily child-free nodes) or exactly two children (the ones who doubled down on parenting). So, if a node isn't a leaf, it's definitely a parent of twins.

Naturally, if a binary tree isn't following these strict twin-or-nothing rules, it's deemed improper. These are the nodes with just one child, perhaps sending their single offspring off to play alone while their proper cousins have a built-in playmate. They're not "wrong," just... less committed to the "full" family ideal.

The Binary Tree Abstract Data Type

left(p): Returns the position of the left child of p (or null if p has no left child).

right(p): Returns the position of the right child of p (or null if p has no right child).

sibling(p): Returns the position of the sibling of p (or null if p has no sibling).

Next, we will define an interface for this ADT. Create the BinaryTree.java file and add the following code:

public interface BinaryTree<E> extends Tree<E> {
    Position<E> left(Position<E> p) throws IllegalArgumentException;

    Position<E> right(Position<E> p) throws IllegalArgumentException;

    Position<E> sibling(Position<E> p) throws IllegalArgumentException;
}

Abstract Binary Tree

Next, we'll create an abstract class, AbstractBinaryTree, that serves as a base for all binary tree implementations. This class will include common methods like sibling(), children() and numChildren() . Create the AbstractBinaryTree.java file and add the following code:

import java.util.ArrayList;
import java.util.List;

public abstract class AbstractBinaryTree<E> extends AbstractTree<E> implements BinaryTree<E> {
        @Override
      public Position<E> sibling(Position<E> p) throws IllegalArgumentException {
          Position<E> parent = parent(p);
          if (parent == null)
              return null;
          if (p == left(parent))
              return right(parent);
          else
              return right(parent);
      }

      @Override
      public Iterable<Position<E>> children(Position<E> p) throws IllegalArgumentException {
          List<Position<E>> snapshot = new ArrayList<>(2);
          if (left(p) != null)
              snapshot.add(left(p));
          if (right(p) != null)
              snapshot.add(right(p));

          return snapshot;
      }

      @Override
    public int numChildren(Position<E> p) throws IllegalArgumentException {
        int count = 0;
        if (left(p) != null)
            count++;
        if (right(p) != null)
            count++;

        return count;
    }
}

Linked Binary Tree

A structure with a node that maintains references to the element stored at a position p and to the nodes associated with the children and parent of p. If p is the root of T, then the parent field of p is null.

Furthermore, each node within it holds reference nodes to its respective left and right child nodes.

Now that we've covered the definitions, it's time for implementation! Begin by creating LinkedBinaryTree.java and inserting the following code:

public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> {
        public LinkedBinaryTree() {
    }
}

Next, add this code in LinkedBinaryTree class.

 protected static class Node<E> implements Position<E> {
        private E element;
        private Node<E> parent;
        private Node<E> left;
        private Node<E> right;

        public Node(E element, Node<E> parent, Node<E> left, Node<E> right) {
            this.element = element;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }

        @Override
        public E getElement() throws IllegalStateException {
            return element;
        }

        public void setElement(E element) {
            this.element = element;
        }

        public Node<E> getParent() {
            return parent;
        }

        public void setParent(Node<E> parent) {
            this.parent = parent;
        }

        public Node<E> getLeft() {
            return left;
        }

        public void setLeft(Node<E> left) {
            this.left = left;
        }

        public Node<E> getRight() {
            return right;
        }

        public void setRight(Node<E> right) {
            this.right = right;
        }

    }

    protected Node<E> createNode(E e, Node<E> parent, Node<E> left, Node<E> right) {
        return new Node<E>(e, parent, left, right);
    }

    protected Node<E> root = null;
    private int size = 0;

Here we create an inner class Node that implements Position interface (defined previously). we also initialize the root and size of the tree. The method createNode is used to create a new instance of node.

• Accessor Methods

  Write the following code:
  

   protected Node<E> validate(Position<E> p) throws IllegalArgumentException {
      if (!(p instanceof Node))
          throw new IllegalArgumentException("Not valid position type");
      Node<E> node = (Node<E>) p;
      if (node.getParent() == node)
          throw new IllegalArgumentException("p is no longer in the tree");
      return node;
  }
  
  @Override
  public Position<E> left(Position<E> p) throws IllegalArgumentException {
      Node<E> node = validate(p);
      return node.getLeft();
  }
  
  @Override
  public Position<E> right(Position<E> p) throws IllegalArgumentException {
      Node<E> node = validate(p);
      return node.getRight();
  }
  
  @Override
  public Position<E> root() {
      return root;
  }
  
  @Override
  public Position<E> parent(Position<E> p) throws IllegalArgumentException {
      Node<E> node = validate(p);
      return node.getParent();
  }
  
  @Override
  public int size() {
      return size;
  }
  
  

  we use validate method to verify if the position is an instance of Node and if the node exists.

• Operative Methods

  These methods facilitate operations such as adding, updating, and removing elements.

  addRoot(e): Creates a root for an empty tree, storing e as the element, and returns the position of that root; an error occurs if the tree is not empty.

  addLeft(p, e): Creates a left child of position p, storing element e, and returns the position of the new node; an error occurs if p already has a left child.

  addRight(p, e): Creates a right child of position p, storing element e, and returns the position of the new node; an error occurs if p already has a right child.

  set(p, e): Replaces the element stored at position p with element e, and returns the previously stored element.

  remove(p): Removes the node at position p, replacing it with its child (if any), and returns the element that had been stored at p an error occurs if p has two children.

  Let's implement the methods we just discussed. Insert the following code on LinkedBinaryTree.java class.
  

  public Position<E> addRoot(E e) throws IllegalStateException {
      if (!isEmpty())
          throw new IllegalStateException("Tree is not empty");
      root = createNode(e, null, null, null);
      size = 1;
      return root;
  }
  
  public Position<E> addLeft(Position<E> p, E e) throws IllegalArgumentException {
      Node<E> parent = validate(p);
      if (parent.getLeft() != null)
          throw new IllegalArgumentException("p already has a left child");
      Node<E> child = createNode(e, parent, null, null);
      parent.setLeft(child);
      size++;
  
      return child;
  }
  
  public Position<E> addRight(Position<E> p, E e) throws IllegalArgumentException {
      Node<E> parent = validate(p);
      if (parent.getRight() != null)
          throw new IllegalArgumentException("p already has a right child");
      Node<E> child = createNode(e, parent, null, null);
      parent.setRight(child);
      size++;
  
      return child;
  }
  
  public E set(Position<E> p, E e) throws IllegalArgumentException {
      Node<E> node = validate(p);
      E temp = node.getElement();
      node.setElement(e);
      return temp;
  }
  
   public E remove(Position<E> p) throws IllegalArgumentException {
      Node<E> node = validate(p);
      if (numChildren(p) == 2)
          throw new IllegalArgumentException("p has two children");
      Node<E> child = node.getLeft() != null ? node.getLeft() : node.getRight();
  
      if (child != null)
          child.setParent(node.getParent());
      if (node == root)
          root = child;
      else {
          Node<E> parent = node.getParent();
          if (node == parent.getLeft())
              parent.setLeft(child);
          else
              parent.setRight(child);
      }
      size--;
      E temp = node.getElement();
      node.setElement(null);
      node.setLeft(null);
      node.setRight(null);
      node.setParent(null);
      return temp;
  }
  
  

• Traversal

  Since we've already implemented general tree traversal methods in AbstractTree.java, we will now focus specifically on inorder traversal. This is the primary traversal method used for binary trees. To implement inorder traversal, add the following code to the AbstractBinaryTree class:
  

  private void inorderSubtree(Position<E> p, List<Position<E>> snapshot) {
      if (left(p) != null)
          inorderSubtree(left(p), snapshot);
  
      snapshot.add(p);
      if (right(p) != null)
          inorderSubtree(right(p), snapshot);
  }
  
  public List<Position<E>> inorder() {
      List<Position<E>> snapshot = new ArrayList<>();
      if (!isEmpty())
          inorderSubtree(root(), snapshot);
      return snapshot;
  }
  
  @Override
  public Iterable<Position<E>> positions() {
      return inorder();
  }
  

💡 The positions method is implemented here to ensure that inorder traversal serves as the default traversal method for the LinkedBinaryTree class. This method can be overridden to provide an alternative traversal implementation.

💡 With the tree implementation complete, it's time to test it out! Navigate to Main.java and insert this code into your main method

public static void main(String[] args) {
    LinkedBinaryTree<Integer> bi = new LinkedBinaryTree<>();

      Position<Integer> one = bi.addRoot(1);
      Position<Integer> left2 = bi.addLeft(one, 2);
      bi.addLeft(left2, 4);

      Position<Integer> right = bi.addRight(one, 3);
      bi.addRight(right, 6);

      bi.addRight(left2, 5);

      var pre = bi.preorder();

      for (Position<Integer> integer : pre) {
          System.out.print(integer.getElement() + ", ");
      }
      System.out.println();
      var post = bi.postorder();

      for (Position<Integer> integer : post) {
          System.out.print(integer.getElement() + ", ");
      }

      System.out.println();
      var bfs = bi.breadthfirst();
      for (Position<Integer> integer : bfs) {
          System.out.print(integer.getElement() + ", ");
      }

      System.out.println();
      var inorder = bi.positions();
      for (Position<Integer> integer : inorder) {
          System.out.print(integer.getElement() + ", ");
      }
}