I'm trying to find a way to realize binary tree traversal using recursion in C or C++ language.
I can implement breath-first traversal (reading each level) with iterative algorithm using queue or smth. else, but i need an algo to do this with recursion.
So problem is: For each level print index of level (0-based) and node infos.
Example: Level 0: A Level 1: B C
Thanks
Here is sample code
/* Function to print level order traversal a tree*/
void printLevelOrder(struct node* root)
{
int h = height(root);
int i;
for(i=1; i<=h; i++)
printGivenLevel(root, i);
}
/* Print nodes at a given level */
void printGivenLevel(struct node* root, int level)
{
if(root == NULL)
return;
if(level == 1)
printf("%d ", root->data);
else if (level > 1)
{
printGivenLevel(root->left, level-1);
printGivenLevel(root->right, level-1);
}
}
The solution is available here http://www.geeksforgeeks.org/level-order-tree-traversal/
Here is a JavaScript Implementation that fakes the output of Breadth First Traversal that you're asking for, but with Depth First recursion. I'm storing the node values at each depth inside an array, inside of a hash. If a level already exists(we have a collision), so we just push to the array at that level. You could use an array instead of a JavaScript object as well since our levels are numeric and can serve as array indices. You can return nodes, values, convert to a Linked List, or whatever you want. I'm just returning values for the sake of simplicity.
BinarySearchTree.prototype.breadthFirstRec = function() {
var levels = {};
var traverse = function(current, depth) {
if (!current) return null;
if (!levels[depth]) levels[depth] = [current.value];
else levels[depth].push(current.value);
traverse(current.left, depth + 1);
traverse(current.right, depth + 1);
};
traverse(this.root, 0);
return levels;
};
var bst = new BinarySearchTree();
bst.add(20, 22, 8, 4, 12, 10, 14, 24);
console.log('Recursive Breadth First: ', bst.breadthFirstRec());
/*Recursive Breadth First:
{ '0': [ 20 ],
'1': [ 8, 22 ],
'2': [ 4, 12, 24 ],
'3': [ 10, 14 ] } */
Here is an example of actual Breadth First Traversal using an iterative approach, in JavaScript, in case anyone is interested. JavaScript rules!
BinarySearchTree.prototype.breadthFirst = function() {
var result = '',
queue = [],
current = this.root;
if (!current) return null;
queue.push(current);
while (current = queue.shift()) {
result += current.value + ' ';
current.left && queue.push(current.left);
current.right && queue.push(current.right);
}
return result;
};
console.log('Breadth First: ', bst.breadthFirst());
//Breadth First: 20 8 22 4 12 24 10 14
I implemented it this way. Tested it for basic conditions only, not fully.
public class Node {
int data;
Node left, right;
Node(int data){
this.data = data;
}
/**
* Searches through the tree for appropiate position of the value to be inserted and inserts it.
* @param data
*/
public void insert(int newValue) {
if(newValue < data) {
if(left == null) {
left = new Node(newValue);
}else {
left.insert(newValue);
}
}else {
if(right == null) {
right = new Node(newValue);
}else {
right.insert(newValue);
}
}
}
public void bfs(boolean isStartingLevel) {
if(isStartingLevel) {
System.out.println(data);
}
if(left != null) {
System.out.println(left.data);
}
if(right != null) {
System.out.println(right.data);
}
if(left != null) {
left.bfs(false);
}
if(right != null) {
right.bfs(false);
}
}
public static void main(String[] args) {
Node n1 = new Node(7);
Node n2 = n1;
n1.insert(9); // right of 7
n1.insert(4); // left of 7
//n1.insert(3); // left of 4
n1.insert(5); // right of 4
//n1.insert(10); // right of 9
n1.insert(8); // left of 9
n2.bfs(true);
}
}
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list=new ArrayList<>();
traverse(root,list,0);
return list;
}
void traverse(TreeNode root, List<List<Integer>> list,int level)
{
if(root==null) //if root is null return
return;
if(list.size()<(level+1))
list.add(new ArrayList<>());
list.get(level).add(root.val);
traverse(root.left,list,level+1);
traverse(root.right,list,level+1);
}
}
/* Input- [3,9,20,null,null,15,7] */
/* Output [[3],[9,20],[15,7]] */
