Trees
For this implementation of the tree, one assumes that each node can have any number of child nodes.
This implementation of the tree contains its own breadth-first and depth-first search algorithms.
Typical breadth-first search algorithms implement queues for storing nodes, and depth-first search algorithms use stacks.
For the depth-first search, this implementation utilizes a recursive process that searches the current node's child nodes until it has reached a leaf.
Java
Node for Tree
TreeNode.java
import java.util.ArrayList;
public class TreeNode {
int data;
TreeNode parent = null;
ArrayList<TreeNode> children = new ArrayList<TreeNode>();
ArrayList<TreeNode> breadthQueue = new ArrayList<TreeNode>();
public TreeNode(int d) {
data = d;
}
TreeNode addChild(int d) {
System.out.println("Adding child " + d + "...");
TreeNode child = new TreeNode(d);
children.add(child);
child.setParent(this);
return child;
}
void setParent(TreeNode newParent) {
parent = newParent;
}
void printTree() {
TreeNode n = this;
printSubTree(n, 0);
System.out.println();
}
int printSubTree(TreeNode n, int level) {
for (int a = 0; a < level; a++) {
System.out.print("-----");
}
System.out.println(n.data);
if (n.children.size() == 0) {
return n.data;
}
int size = n.children.size();
level++;
for (int i = 0; i < size; i++) {
printSubTree(n.children.get(i), level);
}
return -1;
}
void depthSearch() {
System.out.println("Depth-first search:");
TreeNode n = this;
depthSearchNode(n);
System.out.println();
System.out.println();
}
void depthSearchNode(TreeNode n) {
System.out.print(n.data + " ");
if (n.children.size() > 0) {
int size = n.children.size();
for (int i = 0; i < size; i++) {
depthSearchNode(n.children.get(i));
}
}
}
void breadthSearch() {
System.out.println("Breadth-first search:");
TreeNode n = this;
breadthQueue.add(n);
while (breadthQueue.size() > 0) {
breadthSearchOneLevel();
}
System.out.println();
System.out.println();
}
void breadthSearchOneLevel() {
TreeNode n = breadthQueue.get(0);
System.out.print(n.data + " ");
breadthQueue.remove(0);
if (n.children.size() > 0) {
int size = n.children.size();
for (int i = 0; i < size; i++) {
breadthQueue.add(n.children.get(i));
}
}
}
}
Implementation of Tree
ImplementTree.java
public class ImplementTree {
public static void main(String[] args) {
System.out.println("Initializing Tree with " + 1);
TreeNode root = new TreeNode(1);
root.printTree();
TreeNode a = root.addChild(2);
root.printTree();
TreeNode b = root.addChild(3);
root.printTree();
a.addChild(4);
root.printTree();
TreeNode c = a.addChild(5);
root.printTree();
c.addChild(6);
root.printTree();
b.addChild(7);
root.printTree();
root.breadthSearch();
root.depthSearch();
}
}
C++
Header File for Tree Node
TreeNode.h
#include <iostream>
#include <vector>
using namespace std;
class TreeNode {
public:
int data;
TreeNode *parent = NULL;
vector<TreeNode *> children;
vector<TreeNode *> breadthQueue;
TreeNode(int d) {
data = d;
}
~TreeNode() {};
TreeNode *addChild(int d);
void setParent(TreeNode *newParent);
void printTree();
int printSubTree(TreeNode *n, int level);
void depthSearch();
void depthSearchNode(TreeNode *n);
void breadthSearch();
void breadthSearchOneLevel();
};
Node for Tree
TreeNode.cpp
#include "TreeNode.h"
TreeNode *TreeNode::addChild(int d) {
cout << "Adding child " << d << "...\n";
TreeNode *child = new TreeNode(d);
children.push_back(child);
child->setParent(this);
return child;
}
void TreeNode::setParent(TreeNode *newParent) {
parent = newParent;
}
void TreeNode::printTree() {
TreeNode *n = this;
printSubTree(n, 0);
cout << "\n";
}
int TreeNode::printSubTree(TreeNode *n, int level) {
int a;
for (a = 0; a < level; a++) {
cout << "-----";
}
cout << n->data << "\n";
if (n->children.size() == 0) {
return n->data;
}
int size = n->children.size();
level++;
int i;
for (int i = 0; i < size; i++) {
printSubTree(n->children.at(i), level);
}
return -1;
}
void TreeNode::depthSearch() {
cout << "Depth-first search:\n";
TreeNode *n = this;
depthSearchNode(n);
cout << "\n";
}
void TreeNode::depthSearchNode(TreeNode *n) {
cout << n->data << " ";
if (n->children.size() > 0) {
int size = n->children.size();
int i;
for (i = 0; i < size; i++) {
depthSearchNode(n->children.at(i));
}
}
}
void TreeNode::breadthSearch() {
cout << "Breadth-first search:\n";
TreeNode *n = this;
breadthQueue.push_back(n);
while(breadthQueue.size() > 0) {
breadthSearchOneLevel();
}
cout << "\n\n";
}
void TreeNode::breadthSearchOneLevel() {
TreeNode *n = this->breadthQueue.at(0);
cout << n->data << " ";
this->breadthQueue.erase(breadthQueue.begin() + 0);
if (n->children.size() > 0) {
int size = n->children.size();
int i;
for (i = 0; i < size; i++) {
breadthQueue.push_back(n->children.at(i));
}
}
}
Implementation of Tree
ImplementQueue.cpp
#include "Queue.h"
int main() {
cout << "Initializing Queue with " << 1 << "\n";
Queue *queue = new Queue(1);
queue->printQueue();
queue->enqueue(2);
queue->enqueue(3);
queue->enqueue(4);
queue->enqueue(5);
queue->dequeue();
queue->enqueue(6);
queue->enqueue(7);
queue->dequeue();
queue->enqueue(8);
return 0;
}
C
Header File for Tree Node
TreeNode_c.h
#include <stdio.h>
#include <stdlib.h>
typedef struct Children {
struct TreeNode **array;
int size;
} Children;
typedef struct BreadthQueue {
struct TreeNode **array;
int size;
} BreadthQueue;
typedef struct TreeNode {
int data;
struct TreeNode *parent;
struct Children children;
struct BreadthQueue breadthQueue;
} TreeNode;
TreeNode* addChild(TreeNode *currentTree, int d);
void setParent(TreeNode *currentTree, TreeNode *newParent);
void printTree(TreeNode *currentTree);
int printSubTree(TreeNode *n, int level);
void depthSearch(TreeNode *currentTree);
void depthSearchNode(TreeNode *n);
void breadthSearch(TreeNode *currentTree);
struct BreadthQueue breadthSearchOneLevel(TreeNode *currentTree, struct BreadthQueue breadthQueue);
struct BreadthQueue breadthQueue_remove(struct BreadthQueue breadthQueue, int index);
Node for Tree
TreeNode.c
#include "TreeNode_c.h"
TreeNode* addChild(TreeNode *currentTree, int d) {
printf("Adding child %d...\n", d);
TreeNode *child = malloc(sizeof(TreeNode));
child->data = d;
if (currentTree->children.size == 0) {
currentTree->children.array = malloc(100 * sizeof(TreeNode));
}
currentTree->children.array[currentTree->children.size] = child;
currentTree->children.size++;
setParent(child, currentTree);
return child;
}
void setParent(TreeNode *currentTree, TreeNode *newParent) {
currentTree->parent = newParent;
}
void printTree(TreeNode *currentTree) {
TreeNode *n = currentTree;
printSubTree(n, 0);
printf("\n");
}
int printSubTree(TreeNode *n, int level) {
int a;
for (a = 0; a < level; a++) {
printf("-----");
}
printf("%d\n", n->data);
if (n->children.size == 0) {
return n->data;
}
int size = n->children.size;
level++;
int i;
for (i = 0; i < size; i++) {
printSubTree(n->children.array[i], level);
}
return -1;
}
void depthSearch(TreeNode *currentTree) {
printf("Depth-first search:\n");
TreeNode *n = currentTree;
depthSearchNode(n);
printf("\n\n");
}
void depthSearchNode(TreeNode *n) {
printf("%d ", n->data);
if (n->children.size > 0) {
int size = n->children.size;
int i;
for (i = 0; i < size; i++) {
depthSearchNode(n->children.array[i]);
}
}
}
void breadthSearch(TreeNode *currentTree) {
printf("Breadth-first search:\n");
TreeNode *n = currentTree;
currentTree->breadthQueue.array = malloc(100 * sizeof(TreeNode));
currentTree->breadthQueue.size = 0;
currentTree->breadthQueue.array[currentTree->breadthQueue.size] = n;
currentTree->breadthQueue.size++;
while (currentTree->breadthQueue.size > 0) {
currentTree->breadthQueue = breadthSearchOneLevel(currentTree, currentTree->breadthQueue);
if (currentTree->breadthQueue.size > 10) {
break;
}
}
printf("\n\n");
}
struct BreadthQueue breadthSearchOneLevel(TreeNode *currentTree, struct BreadthQueue breadthQueue) {
TreeNode *n = breadthQueue.array[0];
printf("%d ", n->data);
currentTree->breadthQueue = breadthQueue_remove(breadthQueue, 0);
if (n->children.size > 0) {
int size = n->children.size;
int i;
for (i = 0; i < size; i++) {
currentTree->breadthQueue.array[currentTree->breadthQueue.size] = n->children.array[i];
currentTree->breadthQueue.size++;
}
}
return currentTree->breadthQueue;
}
struct BreadthQueue breadthQueue_remove(struct BreadthQueue breadthQueue, int index) {
if (index <= breadthQueue.size - 1) {
int i;
for (i = index; i < breadthQueue.size - 1; i++) {
breadthQueue.array[i] = breadthQueue.array[i + 1];
}
}
breadthQueue.size--;
return breadthQueue;
}
Implementation of Tree
ImplementTree.c
#include "TreeNode_c.h"
int main() {
printf("Initializing Tree with %d\n", 1);
TreeNode *root = malloc(sizeof(TreeNode));
root->data = 1;
printTree(root);
TreeNode *a = addChild(root, 2);
printTree(root);
TreeNode *b = addChild(root, 3);
printTree(root);
addChild(a, 4);
printTree(root);
TreeNode *c = addChild(a, 5);
printTree(root);
addChild(c, 6);
printTree(root);
addChild(b, 7);
printTree(root);
breadthSearch(root);
depthSearch(root);
return 0;
}
C#
Node for Tree
TreeNode.cs
using System;
using System.Collections.Generic;
public class TreeNode
{
int data;
TreeNode parent = null;
List<TreeNode> children = new List<TreeNode>();
List<TreeNode> breadthQueue = new List<TreeNode>();
public TreeNode(int d)
{
data = d;
}
public TreeNode addChild(int d)
{
Console.WriteLine("Adding child " + d + "...");
TreeNode child = new TreeNode(d);
children.Add(child);
child.setParent(this);
return child;
}
public void setParent(TreeNode newParent)
{
parent = newParent;
}
public void printTree()
{
TreeNode n = this;
printSubTree(n, 0);
Console.WriteLine();
}
int printSubTree(TreeNode n, int level)
{
for (int a = 0; a < level; a++)
{
Console.Write("-----");
}
Console.WriteLine(n.data);
if (n.children.Count == 0)
{
return n.data;
}
int size = n.children.Count;
level++;
for (int i = 0; i < size; i++)
{
printSubTree(n.children[i], level);
}
return -1;
}
public void depthSearch()
{
Console.WriteLine("Depth-first search:");
TreeNode n = this;
depthSearchNode(n);
Console.WriteLine();
Console.WriteLine();
}
public void depthSearchNode(TreeNode n)
{
Console.Write(n.data + " ");
if (n.children.Count > 0)
{
int size = n.children.Count;
for (int i = 0; i < size; i++)
{
depthSearchNode(n.children[i]);
}
}
}
public void breadthSearch()
{
Console.WriteLine("Breadth-first search:");
TreeNode n = this;
breadthQueue.Add(n);
while (breadthQueue.Count > 0)
{
breadthSearchOneLevel();
}
Console.WriteLine();
Console.WriteLine();
}
public void breadthSearchOneLevel()
{
TreeNode n = breadthQueue[0];
Console.Write(n.data + " ");
breadthQueue.RemoveAt(0);
if (n.children.Count > 0)
{
int size = n.children.Count;
for (int i = 0; i < size; i++)
{
breadthQueue.Add(n.children[i]);
}
}
}
}
Implementation of Tree
ImplementTree.cs
using System;
public class ImplementTree
{
public static void Main()
{
Console.WriteLine("Initializing Tree with " + 1);
TreeNode root = new TreeNode(1);
root.printTree();
TreeNode a = root.addChild(2);
root.printTree();
TreeNode b = root.addChild(3);
root.printTree();
a.addChild(4);
root.printTree();
TreeNode c = a.addChild(5);
root.printTree();
c.addChild(6);
root.printTree();
b.addChild(7);
root.printTree();
root.breadthSearch();
root.depthSearch();
}
}
Console Output:
ImplementList.cpp
Initializing Tree with 1
1
Adding child 2...
1
-----2
Adding child 3...
1
-----2
-----3
Adding child 4...
1
-----2
----------4
-----3
Adding child 5...
1
-----2
----------4
----------5
-----3
Adding child 6...
1
-----2
----------4
----------5
---------------6
-----3
Adding child 7...
1
-----2
----------4
----------5
---------------6
-----3
----------7
Breadth-first search:
1 2 3 4 5 7 6
Depth-first search:
1 2 4 5 6 3 7
Notes
Data Structures
Algorithms
OOP
Practice Problems
Project Euler
LeetCode