Tree Traversal

Trees are naturally recursive data structures, and because of this, we cannot access their elements like we might access the elements of a vector or array. Instead, we need to use more interesting methods to work through each element. This is often called Tree Traversal, and there are many different ways to do this. For now, we will restrict the discussion to two common and related methods of tree traversal: Depth-First and Breadth-First Search. Note that trees vary greatly in shape and size depending on how they are used; however, they are composed primarily of nodes that house other, children nodes, like so:

struct Node
    children::Vector{Node}
    ID::Int64
    Node(ID::Int64) = new(Vector{Node}(), ID)
end
struct node {
  std::vector<node> children;
  int value;
};
public class Tree
{
    public int Id { get; private set; }
    private List<Tree> _children = new List<Tree>();
struct node {
    struct node *children;
    size_t children_size;
    int id;
};
private class Node implements Comparable<Node> {
    public ArrayList<Node> children;
    public int id;

    public Node(int id) {
        this.children = new ArrayList<Node>();
        this.id = id;
    }

    @Override
    public int compareTo(Node other) {
        // Need to implement Comparable<Node> and override this
        // method because of the method BFSQueue() which uses Queues
        // and must know how to check if two nodes are the same or not
        return Integer.compare(this.id, other.id);
    }
}

This has not been implemented in your chosen language, so here is the Julia code

struct Node
    children::Vector{Node}
    ID::Int64
    Node(ID::Int64) = new(Vector{Node}(), ID)
end
class Node:
    def __init__(self):
        self.data = None
        self.children = []

struct Node {
    children: Vec<Node>,
    value: u64,
}
data Tree a = Node { node :: a
                   , forest :: [Tree a]
                   } deriving (Show)
class Node {
    var value: Int
    var children: [Node]?

    init(value: Int, children: [Node]) {
        self.value = value
        self.children = children
    }
}

Because of this, the most straightforward way to traverse the tree might be recursive. This naturally leads us to the Depth-First Search (DFS) method:

function DFS_recursive(n::Node)
    # Here we are doing something...
    println(n.ID)

    for child in n.children
        DFS_recursive(child)
    end
end
// Simple recursive scheme for DFS
void dfs_recursive(node const& n) {
  // Here we are doing something...
  std::cout << n.value << '\n';
  for (auto const& child : n.children) {
    dfs_recursive(child);
  }
}
public void DFSRecursive()
{
    DFSRecursive(this);

    void DFSRecursive(Tree tree)
    {
        Console.WriteLine(tree.Id);

        foreach (var c in tree._children)
            DFSRecursive(c);
    }
}
void dfs_recursive(struct node n) {
    printf("%d\n", n.id);

    if (n.children) {
        for (size_t i = 0; i < n.children_size; ++i) {
            dfs_recursive(n.children[i]);
        }
    }
}
private void dfsRecursive(Node node) {
    System.out.println(node.id);

    for (Node n : node.children) {
        dfsRecursive(n);
    }
}
function dfsPreorder(tree) {
  console.log(tree.id);
  tree.children.forEach(dfsPreorder);
}
def DFS_recursive(node):
    if node.data != None:
        print(node.data)

    for child in node.children:
        DFS_recursive(child)

fn dfs_recursive(n: &Node) {
    println!("{}", n.value);

    for child in &n.children {
        dfs_recursive(child);
    }
}
dfs :: Tree a -> [a]
dfs (Node x ts) = x : concatMap dfs ts
func dfsRecursive(node: Node) {
    print(node.value)

    for child in node.children! {
        dfsRecursive(node: child)
    }
}

At least to me, this makes a lot of sense. We fight recursion with recursion! First, we first output the node we are on and then we call DFS_recursive(...) on each of its children nodes. This method of tree traversal does what its name implies: it goes to the depths of the tree first before going through the rest of the branches. In this case, the ordering looks like:

Note that the in the code above, we are missing a crucial step: checking to see if the node we are using actually exists! Because we are using a vector to store all the nodes, we will be careful not to run into a case where we call DFS_recursive(...) on a node that has yet to be initialized; however, depending on the language we are using, we might need to be careful of this to avoid recursion errors!

Now, in this case the first element searched through is still the root of the tree. This type of tree traversal is known as pre-order DFS. We perform an action (output the ID) before searching through the children. If we shift the function around and place the data output at the end of the function, we can modify the order in which we search through the tree to be post-order and look something like this:

function DFS_recursive_postorder(n::Node)

    for child in n.children
        DFS_recursive_postorder(child)
    end

    # Here we are doing something...
    println(n.ID)
end

This has not been implemented in your chosen language, so here is the Julia code

function DFS_recursive_postorder(n::Node)

    for child in n.children
        DFS_recursive_postorder(child)
    end

    # Here we are doing something...
    println(n.ID)
end
public void DFSRecursivePostorder()
{
    DFSRecursivePostorder(this);

    void DFSRecursivePostorder(Tree tree)
    {
        foreach (var c in tree._children)
            DFSRecursivePostorder(c);

        Console.WriteLine(tree.Id);
    }
}
void dfs_recursive_postorder(struct node n) {
    for (size_t i = 0; i < n.children_size; ++i) {
        dfs_recursive_postorder(n.children[i]);
    }

    printf("%d\n", n.id);
}
private void dfsRecursivePostOrder(Node node) {
    for (Node n : node.children) {
        dfsRecursivePostOrder(n);
    }

    // Here we are doing something ...
    System.out.println(node.id);
}
function dfsPostorder(tree) {
  tree.children.forEach(dfsPostorder);
  console.log(tree.id);
}
def DFS_recursive_postorder(node):
    for child in node.children:
        DFS_recursive_postorder(child)

    if node.data != None:
        print(node.data)

fn dfs_recursive_postorder(n: &Node) {
    for child in &n.children {
        dfs_recursive_postorder(child);
    }

    println!("{}", n.value);
}
dfsPostOrder :: Tree a -> [a]
dfsPostOrder (Node x ts) = concatMap dfsPostOrder ts ++ [x]
func dfsRecursivePostOrder(node: Node) {
    for child in node.children! {
        dfsRecursivePostOrder(node: child)
    }

    print(node.value)
}

In this case, the first node visited is at the bottom of the tree and moves up the tree branch by branch. In addition to these two types, binary trees have an in-order traversal scheme that looks something like this:

# This assumes only 2 children, but accounts for other possibilities
function DFS_recursive_inorder_btree(n::Node)

    if (length(n.children) == 2)
        DFS_recursive_inorder_btree(n.children[1])
        println(n.ID)
        DFS_recursive_inorder_btree(n.children[2])
    elseif (length(n.children) == 1)
        DFS_recursive_inorder_btree(n.children[1])
        println(n.ID)
    elseif (length(n.children) == 0)
        println(n.ID)
    else
        println("Not a binary tree!")
    end
end

This has not been implemented in your chosen language, so here is the Julia code

# This assumes only 2 children, but accounts for other possibilities
function DFS_recursive_inorder_btree(n::Node)

    if (length(n.children) == 2)
        DFS_recursive_inorder_btree(n.children[1])
        println(n.ID)
        DFS_recursive_inorder_btree(n.children[2])
    elseif (length(n.children) == 1)
        DFS_recursive_inorder_btree(n.children[1])
        println(n.ID)
    elseif (length(n.children) == 0)
        println(n.ID)
    else
        println("Not a binary tree!")
    end
end
public void DFSRecursiveInorderBinary()
{
    DFSRecursiveInorderBinary(this);

    // This assumes only 2 children
    void DFSRecursiveInorderBinary(Tree tree)
    {
        if (tree._children.Count > 2)
            throw new Exception("Not binary tree!");

        if (tree._children.Count > 0)
        {
            DFSRecursiveInorderBinary(tree._children[0]);
            Console.WriteLine(tree.Id);
            DFSRecursiveInorderBinary(tree._children[1]);
        }
        else
            Console.WriteLine(tree.Id);
    }
}
void dfs_recursive_inorder_btree(struct node n) {
    switch (n.children_size) {
    case 2:
        dfs_recursive_inorder_btree(n.children[0]);
        printf("%d\n", n.id);
        dfs_recursive_inorder_btree(n.children[1]);
        break;
    case 1:
        dfs_recursive_inorder_btree(n.children[0]);
        printf("%d\n", n.id);
        break;
    case 0:
        printf("%d\n", n.id);
        break;
    default:
        printf("This is not a binary tree.\n");
        break;
    }
}
// This assumes only 2 children
private void dfsRecursiveInOrderBinary(Node node) {
    if (node.children.size() > 2) {
        System.err.println("Not a binary tree at dfsRecursiveInOrderBinary()!");
        return;
    }

    if (node.children.size() > 1) {
        dfsRecursiveInOrderBinary(node.children.get(0));
        System.out.println(node.id);
        dfsRecursiveInOrderBinary(node.children.get(1));
    } else {
        System.out.println(node.id);
    }
}
function dfsInorder(tree) {
  if (!tree) {
    return;
  }

  if (tree.children.length > 2) {
    throw new Error("Postorder traversal is only valid for binary trees");
  }

  dfsInorder(tree.children[0]);
  console.log(tree.id);
  dfsInorder(tree.children[1]);
}
# This assumes only 2 children, but accounts for other possibilities
def DFS_recursive_inorder_btree(node):
    if (len(node.children) == 2):
        DFS_recursive_inorder_btree(node.children[0])
        print(node.data)
        DFS_recursive_inorder_btree(node.children[1])
    elif (len(node.children) == 1):
        DFS_recursive_inorder_btree(node.children[0])
        print(node.data)
    elif (len(node.children) == 0):
        print(node.data)
    else:
        print("Not a binary tree!")

fn dfs_recursive_inorder_btree(n: &Node) {
    if n.children.len() == 2{
        dfs_recursive_inorder_btree(&n.children[1]);
        println!("{}", n.value);
        dfs_recursive_inorder_btree(&n.children[0]);
    } else if n.children.len() == 1 {
        dfs_recursive_inorder_btree(&n.children[0]);
        println!("{}", n.value);
    } else if n.children.len() == 0 {
        println!("{}", n.value);
    } else {
        println!("This is not a binary tree.");
    }
}
dfsInOrder :: Tree a -> [a] -- For binary trees only
dfsInOrder (Node x [])     = [x]
dfsInOrder (Node x [l])    = dfsInOrder l ++ [x] -- Single branch assumed to be left
dfsInOrder (Node x [l, r]) = dfsInOrder l ++ [x] ++ dfsInOrder r
dfsInOrder _               = error "Not a binary tree"
func dfsRecursiveInOrderBinary(node: Node) {
    if node.children?.count == 2 {
        dfsRecursiveInOrderBinary(node: node.children![0])
        print(node.value)
        dfsRecursiveInOrderBinary(node: node.children![1])
    } else if node.children?.count == 1 {
        dfsRecursiveInOrderBinary(node: node.children![0])
        print(node.value)
    } else if node.children?.count == 0 {
        print(node.value)
    } else {
        print("Not a binary tree!")
    }
}

The order here seems to be some mix of the other 2 methods and works through the binary tree from left to right.

Now, at this point, it might seem that the only way to search through a recursive data structure is with recursion, but this is not necessarily the case! Rather surprisingly, we can perform a DFS non-recursively by using a stack, which are data structures that hold multiple elements, but only allow you to interact with the very last element you put in. The idea here is simple:

  1. Put the root node in the stack
  2. Take it out and put in its children
  3. Pop the top of the stack and put its children in
  4. Repeat 3 until the stack is empty

In code, it looks like this:

function DFS_stack(n::Node)
    s = Stack(Node)
    push!(s, n)

    while(length(s) > 0)
        println(top(s).ID)
        temp = pop!(s)
        for child in temp.children
            push!(s, child)
        end
    end
end
// Simple non-recursive scheme for DFS
void dfs_stack(node const& n) {
  // this stack holds pointers into n's `children` vector,
  // or its children's `children` vector.
  std::stack<node const*> stack;
  stack.push(&n);

  while (stack.size() > 0) {
    auto const& temp = *stack.top();
    stack.pop();
    std::cout << temp.value << '\n';

    for (auto const& child : temp.children) {
      stack.push(&child);
    }
  }
}
public void DFSStack()
{
    var stack = new Stack<Tree>();
    stack.Push(this);

    while (stack.Count != 0)
    {
        Console.WriteLine(stack.Peek().Id);
        var temp = stack.Pop();

        foreach (var c in temp._children)
            stack.Push(c);
    }
}
void dfs_stack(struct node n) {
    struct stack stk = get_stack(sizeof(struct node*));
    stack_push(&stk, &n);
    struct node *tmp;

    while (!stack_empty(&stk)) {
        tmp = (struct node*)stack_pop(&stk);
        if (!tmp) {
            break;
        }

        printf("%d\n", tmp->id);
        for (size_t i = 0; i < tmp->children_size; ++i) {
            stack_push(&stk, &tmp->children[i]);
        }
    }

    free_stack(stk);
}
public void dfsStack() {
    Stack<Node> stack = new Stack<Node>();
    stack.push(this.root);

    Node tmp;

    while (stack.size() != 0) {
        System.out.println(stack.peek().id);
        tmp = stack.pop();

        for (Node c : tmp.children) {
            stack.push(c);
        }
    }
}
function dfsIterative(tree) {
  const stack = [tree];
  while (stack.length > 0) {
    const current = stack.pop();
    console.log(current.id);
    stack.push(...current.children);
  }
}
def DFS_stack(node):
    stack = []
    stack.append(node)

    temp = None

    while len(stack) > 0:
        print(stack[-1].data)
        temp = stack.pop()

        for child in temp.children:
            stack.append(child)

fn dfs_stack(n: &Node) {
    let mut stack = vec![n];

    while let Some(current) = stack.pop() {
        println!("{}", current.value);
        stack.extend(&current.children);
    }
}

This has not been implemented in your chosen language, so here is the Julia code

function DFS_stack(n::Node)
    s = Stack(Node)
    push!(s, n)

    while(length(s) > 0)
        println(top(s).ID)
        temp = pop!(s)
        for child in temp.children
            push!(s, child)
        end
    end
end
func dfsStack(node: Node) {
    var stack = [node]
    var temp: Node

    while stack.count > 0 {
        temp = stack.popLast()!
        print(temp.value)

        for child in temp.children! {
            stack.append(child)
        }
    }
}

All this said, there are a few details about DFS that might not be idea, depending on the situation. For example, if we use DFS on an incredibly long tree, we will spend a lot of time going further and further down a single branch without searching the rest of the data structure. In addition, it is not the natural way humans would order a tree if asked to number all the nodes from top to bottom. I would argue a more natural traversal order would look something like this:

And this is exactly what Breadth-First Search (BFS) does! On top of that, it can be implemented in the same way as the DFS_stack(...) function above, simply by swapping the stack for a queue, which is similar to a stack, except that it only allows you to interact with the very first element instead of the last. In code, this looks something like:

function BFS_queue(n::Node)
    q = Queue(Node)
    enqueue!(q, n)

    while(length(q) > 0)
        println(front(q).ID)
        temp = dequeue!(q)
        for child in temp.children
            enqueue!(q, child)
        end
    end
end
// simple non-recursive scheme for BFS
void bfs_queue(node const& n) {
  std::queue<node const*> queue;
  queue.push(&n);

  while (queue.size() > 0) {
    auto const& temp = *queue.front();
    queue.pop();

    std::cout << temp.value << '\n';
    for (auto const& child : temp.children) {
      queue.push(&child);
    }
  }
}
public void BFSQueue()
{
    var queue = new Queue<Tree>();
    queue.Enqueue(this);

    while (queue.Count != 0)
    {
        Console.WriteLine(queue.Peek().Id);
        var temp = queue.Dequeue();

        foreach (var c in temp._children)
            queue.Enqueue(c);
    }
}
void bfs_queue(struct node n) {
    struct queue q = get_queue(sizeof(struct node*));
    enqueue(&q, &n);
    struct node *tmp;

    while (!queue_empty(&q)) {
        tmp = (struct node*)dequeue(&q);
        if (!tmp) {
            break;
        }

        printf("%d\n", tmp->id);
        for (size_t i = 0; i < tmp->children_size; ++i) {
            enqueue(&q, &tmp->children[i]);
        }
    }

    free_queue(q);
}
public void bfsQueue() {
    Queue<Node> queue = new PriorityQueue<Node>();
    queue.add(this.root);

    while (queue.size() != 0) {
        System.out.println(queue.peek().id);
        Node temp = queue.poll(); // return null if the queue is empty

        if (temp != null) {
            for (Node c : temp.children) {
                queue.add(c);
            }
        }
    }
}
function bfs(tree) {
  const queue = [tree];
  while (queue.length > 0) {
    const current = queue.shift();
    console.log(current.id);
    queue.push(...current.children);
  }
}
def BFS_queue(node):
    queue = []
    queue.append(node)

    temp = None

    while len(queue) > 0:
        print(queue[0].data)
        temp = queue.pop(0)

        for child in temp.children:
            queue.append(child)

fn bfs_queue(n: &Node){
    let mut queue = VecDeque::new();
    queue.push_back(n);

    while let Some(current) = queue.pop_front() {
        println!("{}", current.value);
        queue.extend(&current.children);
    }
}
bfs :: Tree a -> [a]
bfs (Node x ts) = x : go ts
  where go [] = []
        go ts = map node ts ++ go (concatMap forest ts)
func bfsQueue(node: Node) {
    var queue = [node]
    var temp: Node

    while queue.count > 0 {
        temp = queue.remove(at: 0)
        print(temp.value)

        for child in temp.children! {
            queue.append(child)
        }
    }
}

Example Code

using DataStructures

struct Node
    children::Vector{Node}
    ID::Int64
    Node(ID::Int64) = new(Vector{Node}(), ID)
end

function DFS_recursive(n::Node)
    # Here we are doing something...
    println(n.ID)

    for child in n.children
        DFS_recursive(child)
    end
end

function DFS_recursive_postorder(n::Node)

    for child in n.children
        DFS_recursive_postorder(child)
    end

    # Here we are doing something...
    println(n.ID)
end

# This assumes only 2 children, but accounts for other possibilities
function DFS_recursive_inorder_btree(n::Node)

    if (length(n.children) == 2)
        DFS_recursive_inorder_btree(n.children[1])
        println(n.ID)
        DFS_recursive_inorder_btree(n.children[2])
    elseif (length(n.children) == 1)
        DFS_recursive_inorder_btree(n.children[1])
        println(n.ID)
    elseif (length(n.children) == 0)
        println(n.ID)
    else
        println("Not a binary tree!")
    end
end

function DFS_stack(n::Node)
    s = Stack(Node)
    push!(s, n)

    while(length(s) > 0)
        println(top(s).ID)
        temp = pop!(s)
        for child in temp.children
            push!(s, child)
        end
    end
end

function BFS_queue(n::Node)
    q = Queue(Node)
    enqueue!(q, n)

    while(length(q) > 0)
        println(front(q).ID)
        temp = dequeue!(q)
        for child in temp.children
            enqueue!(q, child)
        end
    end
end

# function to create a simple, balanced tree
function create_tree(num_row::Int64, num_child::Int64)
    ret = Node(num_row)
    if (num_row == 0)
        return ret
    end

    for i = 1:num_child
        child = create_tree(num_row - 1, num_child)
        push!(ret.children, child)
    end

    return ret
end

function main()

    println("Creating Tree")
    root = create_tree(2, 3)

    println("Using recursive DFS:")
    DFS_recursive(root);

    println("Using recursive DFS with post-order traversal:")
    DFS_recursive_postorder(root);

    println("Using stack-based DFS:")
    DFS_stack(root);

    println("Using queue-based BFS:")
    BFS_queue(root);

    println("Creating binary tree to test in-order traversal.")
    root_binary = create_tree(3,2)
    println("Using In-order DFS:")
    DFS_recursive_inorder_btree(root_binary)
end

main()
// initially contributed by James Schloss (Leios)
// restyled by Nicole Mazzuca (ubsan)

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <queue>
#include <stack>
#include <utility>
#include <vector>

using std::size_t;

struct node {
  std::vector<node> children;
  int value;
};

// Simple recursive scheme for DFS
void dfs_recursive(node const& n) {
  // Here we are doing something...
  std::cout << n.value << '\n';
  for (auto const& child : n.children) {
    dfs_recursive(child);
  }
}

// Simple non-recursive scheme for DFS
void dfs_stack(node const& n) {
  // this stack holds pointers into n's `children` vector,
  // or its children's `children` vector.
  std::stack<node const*> stack;
  stack.push(&n);

  while (stack.size() > 0) {
    auto const& temp = *stack.top();
    stack.pop();
    std::cout << temp.value << '\n';

    for (auto const& child : temp.children) {
      stack.push(&child);
    }
  }
}

// simple non-recursive scheme for BFS
void bfs_queue(node const& n) {
  std::queue<node const*> queue;
  queue.push(&n);

  while (queue.size() > 0) {
    auto const& temp = *queue.front();
    queue.pop();

    std::cout << temp.value << '\n';
    for (auto const& child : temp.children) {
      queue.push(&child);
    }
  }
}

node create_tree(size_t num_row, size_t num_child) {
  if (num_row == 0) {
    return node{std::vector<node>(), 0};
  }

  std::vector<node> vec;
  std::generate_n(std::back_inserter(vec), num_child, [&] {
    return create_node(num_row - 1, num_child);
  });

  return node{std::move(vec), num_row};
}

int main() {
  // Creating Tree in main
  auto root = create_node(3, 3);
  dfs_recursive(root);
  dfs_stack(root);
  bfs_queue(root);
}

Tree.cs

// submitted by Julian Schacher (jspp)
using System;
using System.Collections.Generic;

namespace TreeTraversal
{
    public class Tree
    {
        public int Id { get; private set; }
        private List<Tree> _children = new List<Tree>();

        public Tree(int depthCount, int childrenCount)
        {
            this.Id = 1;

            if (!(depthCount <= 1))
            {
                for (int i = 0; i < childrenCount; i++)
                    this._children.Add(new Tree(this.Id * 10 + i + 1, depthCount - 1, childrenCount));
            }
        }

        private Tree(int id, int depthCount, int childrenCount)
        {
            this.Id = id;

            if (!(depthCount <= 1))
            {
                for (int i = 0; i < childrenCount; i++)
                    this._children.Add(new Tree(this.Id * 10 + i + 1, depthCount - 1, childrenCount));
            }
        }

        public void DFSRecursive()
        {
            DFSRecursive(this);

            void DFSRecursive(Tree tree)
            {
                Console.WriteLine(tree.Id);

                foreach (var c in tree._children)
                    DFSRecursive(c);
            }
        }

        public void DFSRecursivePostorder()
        {
            DFSRecursivePostorder(this);

            void DFSRecursivePostorder(Tree tree)
            {
                foreach (var c in tree._children)
                    DFSRecursivePostorder(c);

                Console.WriteLine(tree.Id);
            }
        }

        public void DFSRecursiveInorderBinary()
        {
            DFSRecursiveInorderBinary(this);

            // This assumes only 2 children
            void DFSRecursiveInorderBinary(Tree tree)
            {
                if (tree._children.Count > 2)
                    throw new Exception("Not binary tree!");

                if (tree._children.Count > 0)
                {
                    DFSRecursiveInorderBinary(tree._children[0]);
                    Console.WriteLine(tree.Id);
                    DFSRecursiveInorderBinary(tree._children[1]);
                }
                else
                    Console.WriteLine(tree.Id);
            }
        }

        public void DFSStack()
        {
            var stack = new Stack<Tree>();
            stack.Push(this);

            while (stack.Count != 0)
            {
                Console.WriteLine(stack.Peek().Id);
                var temp = stack.Pop();

                foreach (var c in temp._children)
                    stack.Push(c);
            }
        }

        public void BFSQueue()
        {
            var queue = new Queue<Tree>();
            queue.Enqueue(this);

            while (queue.Count != 0)
            {
                Console.WriteLine(queue.Peek().Id);
                var temp = queue.Dequeue();

                foreach (var c in temp._children)
                    queue.Enqueue(c);
            }
        }
    }
}

Program.cs

// submitted by Julian Schacher (jspp)
using System;

namespace TreeTraversal
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("TreeTraversal");
            var tree = new Tree(3, 3);
            Console.WriteLine("DFSRecursive:");
            tree.DFSRecursive();
            Console.WriteLine("DFSStack:");
            tree.DFSStack();
            Console.WriteLine("BFSQueue:");
            tree.BFSQueue();
            Console.WriteLine("DFSRecursivePostorder");
            tree.DFSRecursivePostorder();

            // Uncommenting the following 2 lines will result in an exception thrown because at least one Node of the Tree has more than 2 children and therefor a DFSRecursiveInorderBinary doesn't work.
            // Console.WriteLine("DFSRecursiveInorder (fail)");
            // tree.DFSRecursiveInorderBinary();
            tree = new Tree(3, 2);
            Console.WriteLine("DFSRecursiveInorder (succeed)");
            tree.DFSRecursiveInorderBinary();
        }
    }
}

utility.h

#ifndef UTILITY_H
#define UTILITY_H

#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>

struct stack {
    void **data;
    size_t top, capacity, size;
};

struct queue {
    void **data;
    size_t front, back, capacity;
};

struct stack get_stack(size_t size) {
    struct stack stk;

    stk.data = malloc(4 * size);
    stk.capacity = 4;
    stk.top = 0;

    return stk;
}

bool stack_empty(struct stack *stk) {
    return stk->top == 0;
}

void stack_push(struct stack *stk, void *element) {
    if (stk->top == stk->capacity) {
        stk->capacity *= 2;
        stk->data = realloc(stk->data, stk->capacity * sizeof(stk->data[0]));
    }

    stk->data[stk->top++] = element;
}

void *stack_pop(struct stack *stk) {
    if (stack_empty(stk)) {
        return NULL;
    }

    return stk->data[--stk->top];
}

void free_stack(struct stack stk) {
    free(stk.data);
}

struct queue get_queue(size_t size) {
    struct queue q;

    q.data = calloc(4, size);
    q.front = 0;
    q.back = 0;
    q.capacity = 4;

    return q;
}

bool queue_empty(struct queue *q) {
    return q->front == q->back;
}

void queue_resize(struct queue *q) {
    size_t size = sizeof(q->data[0]);
    void **tmp = calloc((q->capacity * 2), size);
    memcpy(tmp, q->data + q->front, (q->capacity - q->front) * size);
    memcpy(tmp + q->capacity - q->front, q->data, (q->front - 1) * size);

    q->data = tmp;
    q->back = q->capacity - 1;
    q->front = 0;
    q->capacity *= 2;
}

void enqueue(struct queue *q, void *element) {
    if (q->front == (q->back % q->capacity) + 1) {
        queue_resize(q);
    }

    q->data[q->back] = element;
    q->back = (q->back + 1) % q->capacity;
}

void *dequeue(struct queue *q) {
    if (queue_empty(q)) {
        return NULL;
    }

    void *ret = q->data[q->front];
    q->front = (q->front + 1) % q->capacity;

    return ret;
}

void free_queue(struct queue q) {
    free(q.data);
}

#endif //UTILITY_H

tree_traversal.c

#include "utility.h"

#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>

struct node {
    struct node *children;
    size_t children_size;
    int id;
};

struct node create_tree(int rows, size_t num_children) {
    struct node n = {NULL, 0, rows};

    if (rows > 0) {
        n.children = (struct node*)malloc(num_children * sizeof(struct node));
        n.children_size = num_children;
        for (size_t i = 0; i < num_children; ++i) {
            n.children[i] = create_tree(rows - 1, num_children);
        }
    }

    return n;
}

void destroy_tree(struct node n) {
    if (n.id > 0) {
        for (size_t i = 0; i < n.children_size; ++i) {
            destroy_tree(n.children[i]);
        }

        free(n.children);
    }
}

void dfs_recursive(struct node n) {
    printf("%d\n", n.id);

    if (n.children) {
        for (size_t i = 0; i < n.children_size; ++i) {
            dfs_recursive(n.children[i]);
        }
    }
}

void dfs_recursive_postorder(struct node n) {
    for (size_t i = 0; i < n.children_size; ++i) {
        dfs_recursive_postorder(n.children[i]);
    }

    printf("%d\n", n.id);
}

void dfs_recursive_inorder_btree(struct node n) {
    switch (n.children_size) {
    case 2:
        dfs_recursive_inorder_btree(n.children[0]);
        printf("%d\n", n.id);
        dfs_recursive_inorder_btree(n.children[1]);
        break;
    case 1:
        dfs_recursive_inorder_btree(n.children[0]);
        printf("%d\n", n.id);
        break;
    case 0:
        printf("%d\n", n.id);
        break;
    default:
        printf("This is not a binary tree.\n");
        break;
    }
}

void dfs_stack(struct node n) {
    struct stack stk = get_stack(sizeof(struct node*));
    stack_push(&stk, &n);
    struct node *tmp;

    while (!stack_empty(&stk)) {
        tmp = (struct node*)stack_pop(&stk);
        if (!tmp) {
            break;
        }

        printf("%d\n", tmp->id);
        for (size_t i = 0; i < tmp->children_size; ++i) {
            stack_push(&stk, &tmp->children[i]);
        }
    }

    free_stack(stk);
}

void bfs_queue(struct node n) {
    struct queue q = get_queue(sizeof(struct node*));
    enqueue(&q, &n);
    struct node *tmp;

    while (!queue_empty(&q)) {
        tmp = (struct node*)dequeue(&q);
        if (!tmp) {
            break;
        }

        printf("%d\n", tmp->id);
        for (size_t i = 0; i < tmp->children_size; ++i) {
            enqueue(&q, &tmp->children[i]);
        }
    }

    free_queue(q);
}

int main() {
    struct node root = create_tree(3, 3);
    bfs_queue(root);
    destroy_tree(root);

    return 0;
}

Tree.java

// submitted by xam4lor
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;

public class Tree {
    public Node root;

    public Tree(int rowCount, int childrenCount) {
        // this.root is the root node of the Tree
        this.root = new Node(1);
        this.createAllChildren(this.root, rowCount, childrenCount);
    }


    public void dfsRecursive() {
        this.dfsRecursive(this.root);
    }

    private void dfsRecursive(Node node) {
        System.out.println(node.id);

        for (Node n : node.children) {
            dfsRecursive(n);
        }
    }


    public void dfsRecursivePostOrder() {
        this.dfsRecursivePostOrder(this.root);
    }

    private void dfsRecursivePostOrder(Node node) {
        for (Node n : node.children) {
            dfsRecursivePostOrder(n);
        }

        // Here we are doing something ...
        System.out.println(node.id);
    }


    public void dfsRecursiveInOrderBinary() {
        dfsRecursiveInOrderBinary(this.root);
    }

    // This assumes only 2 children
    private void dfsRecursiveInOrderBinary(Node node) {
        if (node.children.size() > 2) {
            System.err.println("Not a binary tree at dfsRecursiveInOrderBinary()!");
            return;
        }

        if (node.children.size() > 1) {
            dfsRecursiveInOrderBinary(node.children.get(0));
            System.out.println(node.id);
            dfsRecursiveInOrderBinary(node.children.get(1));
        } else {
            System.out.println(node.id);
        }
    }


    public void dfsStack() {
        Stack<Node> stack = new Stack<Node>();
        stack.push(this.root);

        Node tmp;

        while (stack.size() != 0) {
            System.out.println(stack.peek().id);
            tmp = stack.pop();

            for (Node c : tmp.children) {
                stack.push(c);
            }
        }
    }

    public void bfsQueue() {
        Queue<Node> queue = new PriorityQueue<Node>();
        queue.add(this.root);

        while (queue.size() != 0) {
            System.out.println(queue.peek().id);
            Node temp = queue.poll(); // return null if the queue is empty

            if (temp != null) {
                for (Node c : temp.children) {
                    queue.add(c);
                }
            }
        }
    }


    private void createAllChildren(Node node, int rowCount, int childrenCount) {
        if (rowCount <= 1) {
           return; 
        }

        for (int i = 0; i < childrenCount; i++) {
            node.children.add(new Node(node.id * 10 + i + 1));
            createAllChildren(node.children.get(i), rowCount - 1, childrenCount);
        }
    }


    private class Node implements Comparable<Node> {
        public ArrayList<Node> children;
        public int id;

        public Node(int id) {
            this.children = new ArrayList<Node>();
            this.id = id;
        }

        @Override
        public int compareTo(Node other) {
            // Need to implement Comparable<Node> and override this
            // method because of the method BFSQueue() which uses Queues
            // and must know how to check if two nodes are the same or not
            return Integer.compare(this.id, other.id);
        }
    }
}

MainClass.java

//submitted by xam4lor
public class MainClass {
    public static void main(String[] args) {
        System.out.println("Creating Tree");
        Tree tree = new Tree(3, 3);

        System.out.println("Using recursive DFS :");
        tree.dfsRecursive();

        System.out.println("Using stack-based DFS :");
        tree.dfsStack();

        System.out.println("Using queue-based BFS :");
        tree.bfsQueue();

        System.out.println("Using post-order recursive DFS :");
        tree.dfsRecursivePostOrder();


        // Uncommenting the following 2 lines will result in an exception thrown because at least one Node of the Tree has more than 2 children and therefor a DFSRecursiveInorderBinary doesn't work.
        System.out.println("Using in-order binary recursive DFS : (fail)");
        tree.dfsRecursiveInOrderBinary();

        tree = new Tree(3, 2);
        System.out.println("Using in-order binary recursive DFS : (succeed)");
        tree.dfsRecursiveInOrderBinary();


        System.out.println("");
    }
}
function createTree(rows, children) {
  if (rows === 0) {
    return { id: rows, children: [] };
  }

  return {
    id: rows,
    children: [...Array(children).keys()].map(() => createTree(rows - 1, children))
  };
}

function dfsPreorder(tree) {
  console.log(tree.id);
  tree.children.forEach(dfsPreorder);
}

function dfsPostorder(tree) {
  tree.children.forEach(dfsPostorder);
  console.log(tree.id);
}

function dfsInorder(tree) {
  if (!tree) {
    return;
  }

  if (tree.children.length > 2) {
    throw new Error("Postorder traversal is only valid for binary trees");
  }

  dfsInorder(tree.children[0]);
  console.log(tree.id);
  dfsInorder(tree.children[1]);
}

function dfsIterative(tree) {
  const stack = [tree];
  while (stack.length > 0) {
    const current = stack.pop();
    console.log(current.id);
    stack.push(...current.children);
  }
}

function bfs(tree) {
  const queue = [tree];
  while (queue.length > 0) {
    const current = queue.shift();
    console.log(current.id);
    queue.push(...current.children);
  }
}

const root = createTree(3, 3);
dfsPreorder(root);
dfsPostorder(root);
dfsIterative(root);
bfs(root);
class Node:
    def __init__(self):
        self.data = None
        self.children = []


def create_tree(node, num_row, num_child):
    node.data = num_row

    if num_row > 0:
        for i in range(num_child):
            child = create_tree(Node(), num_row-1, num_child)
            node.children.append(child)

    return node


def DFS_recursive(node):
    if node.data != None:
        print(node.data)

    for child in node.children:
        DFS_recursive(child)


def DFS_recursive_postorder(node):
    for child in node.children:
        DFS_recursive_postorder(child)

    if node.data != None:
        print(node.data)


# This assumes only 2 children, but accounts for other possibilities
def DFS_recursive_inorder_btree(node):
    if (len(node.children) == 2):
        DFS_recursive_inorder_btree(node.children[0])
        print(node.data)
        DFS_recursive_inorder_btree(node.children[1])
    elif (len(node.children) == 1):
        DFS_recursive_inorder_btree(node.children[0])
        print(node.data)
    elif (len(node.children) == 0):
        print(node.data)
    else:
        print("Not a binary tree!")


def DFS_stack(node):
    stack = []
    stack.append(node)

    temp = None

    while len(stack) > 0:
        print(stack[-1].data)
        temp = stack.pop()

        for child in temp.children:
            stack.append(child)


def BFS_queue(node):
    queue = []
    queue.append(node)

    temp = None

    while len(queue) > 0:
        print(queue[0].data)
        temp = queue.pop(0)

        for child in temp.children:
            queue.append(child)


def main():
    tree = create_tree(Node(), 3, 3)

    print("Recursive:")
    DFS_recursive(tree)

    print("Recursive Postorder:")
    DFS_recursive_postorder(tree)

    print("Stack:")
    DFS_stack(tree)

    print("Queue:")
    BFS_queue(tree)

    binaryTree = create_tree(Node(), 3, 2)

    print("Recursive Inorder Binary Tree:")
    DFS_recursive_inorder_btree(binaryTree)

if __name__ == '__main__':
    main()

The code snippets were taken from this Scratch project

use std::collections::VecDeque;

#[derive(Debug)]
struct Node {
    children: Vec<Node>,
    value: u64,
}

fn dfs_recursive(n: &Node) {
    println!("{}", n.value);

    for child in &n.children {
        dfs_recursive(child);
    }
}

fn dfs_recursive_postorder(n: &Node) {
    for child in &n.children {
        dfs_recursive_postorder(child);
    }

    println!("{}", n.value);
}

fn dfs_recursive_inorder_btree(n: &Node) {
    if n.children.len() == 2{
        dfs_recursive_inorder_btree(&n.children[1]);
        println!("{}", n.value);
        dfs_recursive_inorder_btree(&n.children[0]);
    } else if n.children.len() == 1 {
        dfs_recursive_inorder_btree(&n.children[0]);
        println!("{}", n.value);
    } else if n.children.len() == 0 {
        println!("{}", n.value);
    } else {
        println!("This is not a binary tree.");
    }
}

fn dfs_stack(n: &Node) {
    let mut stack = vec![n];

    while let Some(current) = stack.pop() {
        println!("{}", current.value);
        stack.extend(&current.children);
    }
}

fn bfs_queue(n: &Node){
    let mut queue = VecDeque::new();
    queue.push_back(n);

    while let Some(current) = queue.pop_front() {
        println!("{}", current.value);
        queue.extend(&current.children);
    }
}

fn create_tree(num_row: u64, num_child: u64) -> Node {
    if num_row == 0 {
        return Node { children: vec![], value: 0 };
    }

    let children = (0..num_child)
        .map(|_| create_tree(num_row - 1, num_child))
        .collect();

    Node { children, value: num_row }
}

fn main() {
    let root = create_tree(2, 3);
    println!("Recursive DFS:");
    dfs_recursive(&root);
    println!("Stack DFS:");
    dfs_stack(&root);
    println!("Queue BFS:");
    bfs_queue(&root);
    println!("Recursive post-order DFS:");
    dfs_recursive_postorder(&root);
    println!("Recursive in-order DFS BTree:");
    let root_binary = create_tree(3, 2);
    dfs_recursive_inorder_btree(&root_binary);
}
data Tree a = Node { node :: a
                   , forest :: [Tree a]
                   } deriving (Show)

dfs :: Tree a -> [a]
dfs (Node x ts) = x : concatMap dfs ts

dfsPostOrder :: Tree a -> [a]
dfsPostOrder (Node x ts) = concatMap dfsPostOrder ts ++ [x]

dfsInOrder :: Tree a -> [a] -- For binary trees only
dfsInOrder (Node x [])     = [x]
dfsInOrder (Node x [l])    = dfsInOrder l ++ [x] -- Single branch assumed to be left
dfsInOrder (Node x [l, r]) = dfsInOrder l ++ [x] ++ dfsInOrder r
dfsInOrder _               = error "Not a binary tree"

bfs :: Tree a -> [a]
bfs (Node x ts) = x : go ts
  where go [] = []
        go ts = map node ts ++ go (concatMap forest ts)

toBin :: Tree a -> Tree a
toBin (Node x ts) = Node x (map toBin $ take 2 ts)

main = do
  print $ dfs testTree
  print $ dfsPostOrder testTree
  print $ dfsInOrder $ toBin testTree
  print $ bfs testTree

testTree :: Tree Int
testTree = Node 1 [ Node 2 [ Node 3 []
                           , Node 4 [ Node 5 []]
                           ]
                  , Node 6 [ Node 7 []
                           , Node 8 [ Node 9 [ Node 10 [ Node 11 []]
                                             , Node 12 []
                                             ]
                                    ]
                           , Node 13 [ Node 14 []]
                           ]
                   , Node 15 []
                   ]
class Node {
    var value: Int
    var children: [Node]?

    init(value: Int, children: [Node]) {
        self.value = value
        self.children = children
    }
}

func createTree(numRows: Int, numChildren: Int) -> Node {
    let node = Node(value: numRows, children: [])

    if numRows > 0 {
        for _ in 1...numChildren {
            let child = createTree(numRows: numRows-1, numChildren: numChildren)
            node.children?.append(child)
        }
    }

    return node
}

func dfsRecursive(node: Node) {
    print(node.value)

    for child in node.children! {
        dfsRecursive(node: child)
    }
}

func dfsRecursivePostOrder(node: Node) {
    for child in node.children! {
        dfsRecursivePostOrder(node: child)
    }

    print(node.value)
}

func dfsRecursiveInOrderBinary(node: Node) {
    if node.children?.count == 2 {
        dfsRecursiveInOrderBinary(node: node.children![0])
        print(node.value)
        dfsRecursiveInOrderBinary(node: node.children![1])
    } else if node.children?.count == 1 {
        dfsRecursiveInOrderBinary(node: node.children![0])
        print(node.value)
    } else if node.children?.count == 0 {
        print(node.value)
    } else {
        print("Not a binary tree!")
    }
}

func dfsStack(node: Node) {
    var stack = [node]
    var temp: Node

    while stack.count > 0 {
        temp = stack.popLast()!
        print(temp.value)

        for child in temp.children! {
            stack.append(child)
        }
    }
}

func bfsQueue(node: Node) {
    var queue = [node]
    var temp: Node

    while queue.count > 0 {
        temp = queue.remove(at: 0)
        print(temp.value)

        for child in temp.children! {
            queue.append(child)
        }
    }
}

func main() {
    let root = createTree(numRows: 3, numChildren: 3)

    print("Using recursive DFS:")
    dfsRecursive(node: root)

    print("Using recursive postorder DFS:")
    dfsRecursivePostOrder(node: root)

    print("Using stack-based DFS:")
    dfsStack(node: root)

    print("Using queue-based BFS:")
    bfsQueue(node: root)

    let rootBinary = createTree(numRows: 3, numChildren: 2)

    print("Using In-order DFS:")
    dfsRecursiveInOrderBinary(node: rootBinary)
}

main()

results matching ""

    No results matching ""