Back to home

Java Trees

Published: Oct 22, 2018

Last updated: Oct 22, 2018

    This is a basic implementation. The bfs and dfs methods each return a List<Integer> of the data stored in each Node to make a comparison in the test.

    Answer

    // src/main/java/Tree.java import main.java.Node; import java.util.ArrayList; import java.util.List; class Tree { public Node root; public Tree() { this.root = null; } public Tree(Node root) { this.root = root; } public List<Integer> bfs() { if (this.root == null) { throw new NullPointerException("this.root is null"); } List<Node> n = new ArrayList<>(); n.add(this.root); List<Integer> res = new ArrayList<>(); while (n.size() > 0) { Node child = n.remove(0); if (child.children != null) { n.addAll(child.children); } res.add(child.data); } return res; } public List<Integer> dfs() { if (this.root == null) { throw new NullPointerException("No root"); } List<Node> n = new ArrayList<Node>(); n.add(this.root); List<Integer> res = new ArrayList<Integer>(); while (n.size() > 0) { Node child = n.remove(0); if (child.children != null) { n.addAll(0, child.children); } res.add(child.data); } return res; } }

    // src/main/java/Node.java package main.java; import java.util.ArrayList; import java.util.List; public class Node { public Integer data; public List<Node> children; public Node() { this.data = null; this.children = new ArrayList<>(); } public Node(Integer data) { this.data = data; this.children = new ArrayList<>(); } public Node(Integer data, List<Node> children) { this.data = data; this.children = new ArrayList<>(); this.children.addAll(children); } }

    // test/java/TreeTest.java import org.junit.Ignore; import org.junit.Test; import java.util.ArrayList; import java.util.List; import static org.junit.Assert.assertEquals; import main.java.Node; public class TreeTest { @Test public void testBFS() { Node n1 = new Node(1); Node n2 = new Node(2); Node n3 = new Node(3); Node n4 = new Node(4); Node n5 = new Node(5); List<Integer> expected = new ArrayList<>(); for (int i = 0; i < 5; i++) { expected.add(i + 1); } Tree t = new Tree(n1); n1.children.add(n2); n1.children.add(n3); n2.children.add(n4); n3.children.add(n5); List<Integer> res = t.bfs(); assertEquals(expected, res); } @Test public void testDFS() { Node n1 = new Node(1); Node n2 = new Node(2); Node n3 = new Node(3); Node n4 = new Node(4); Node n5 = new Node(5); List<Integer> expected = new ArrayList<>(); expected.add(1); expected.add(2); expected.add(4); expected.add(3); expected.add(5); Tree t = new Tree(n1); n1.children.add(n2); n1.children.add(n3); n2.children.add(n4); n3.children.add(n5); List<Integer> res = t.dfs(); assertEquals(expected, res); } }

    Personal image

    Dennis O'Keeffe

    @dennisokeeffe92
    • Melbourne, Australia

    Hi, I am a professional Software Engineer. Formerly of Culture Amp, UsabilityHub, Present Company and NightGuru.
    I am currently working on Visibuild.

    1,200+ PEOPLE ALREADY JOINED ❤️️

    Get fresh posts + news direct to your inbox.

    No spam. We only send you relevant content.

    Java Trees

    Introduction

    Share this post