# Construct N Level Calkin-Wilf Tree

The Calkin-Wilf Tree is a binary tree that represents the sequence of rational numbers in a unique way. Each node of the tree represents a rational number in the form of a fraction `a/b`, where `a` and `b` are coprime (their greatest common divisor is 1). The tree is constructed in such a way that the left child of a node represents the fraction `a/(a+b)` and the right child represents the fraction `(a+b)/b`.

## Problem Statement

The goal is to construct an N-level Calkin-Wilf Tree and print out the rational numbers represented by its nodes in a specific order.

## Example

For a 3-level Calkin-Wilf Tree:

``````    (1/1)
/     \
(1/2)   (2/1)
/  \    /  \
(1/3) (3/2)(2/3)(3/1)``````

## Idea to Solve

The given code implements the construction of an N-level Calkin-Wilf Tree using a recursive approach. It starts with a root node representing the fraction `1/1` and constructs the tree by recursively creating left and right children with the appropriate fractions.

## Algorithm

1. Define a `TreeNode` structure with `a`, `b`, `left`, and `right` pointers.
2. Define a `CalkinWilfTree` structure with a `root` pointer.
3. Implement a `newTree` function that creates a new instance of `CalkinWilfTree`.
4. Implement a `newNode` function that creates a new instance of `TreeNode` with given `a` and `b` values.
5. Implement a `constructTree` function that constructs the Calkin-Wilf Tree recursively.
• If the level is 0, return `NULL`.
• Create a new node with fraction `a/b`.
• Recursively construct the left child with fractions `a/(a+b)` and `(a+b)/b` for the right child.
6. Implement a `makeTree` function that initializes the tree construction with the root fraction `1/1`.
7. Implement a `preorder` function that traverses the tree in preorder and prints the fractions.
8. In the `main` function:
• Set the desired level (e.g., 3).
• Create a new Calkin-Wilf Tree.
• Construct the tree using the `makeTree` function.
• Print the fractions using the `preorder` function.

## Code Solution

``````/*
C program for
Construct N Level Calkin-Wilf Tree
*/
#include <stdio.h>

#include <stdlib.h>
// Tree Node
struct TreeNode
{
int a;
int b;
struct TreeNode *left;
struct TreeNode *right;
};
struct CalkinWilfTree
{
struct TreeNode *root;
};
// Create new tree
struct CalkinWilfTree *newTree()
{
// Create dynamic node
struct CalkinWilfTree *tree =
(struct CalkinWilfTree *) malloc(sizeof(struct CalkinWilfTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
// return new tree
return tree;
}
// This is creating and return new node of tree
struct TreeNode *newNode(int a, int b)
{
// Create dynamic node
struct TreeNode *node =
(struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
node->a = a;
node->b = b;
node->left = NULL;
node->right = NULL;
}
else
{
// This is indicates,
// Segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
// return new node
return node;
}
// This function are constructing a Calkin Wilf Tree
struct TreeNode *constructTree(int a, int b, int level)
{
if (level == 0)
{
return NULL;
}
struct TreeNode *node = newNode(a, b);
//  build left and right subtree by using recursively
node->left = constructTree(a, a + b, level - 1);
node->right = constructTree(a + b, b, level - 1);
return node;
}
struct TreeNode *makeTree(int level)
{
return constructTree(1, 1, level);
}
void preorder(struct TreeNode *node)
{
if (node != NULL)
{
printf(" (%d/%d)", node->a, node->b);
preorder(node->left);
preorder(node->right);
}
}
int main(int argc, char
const *argv[])
{
int level = 3;
struct CalkinWilfTree *tree = newTree();
/*
Level : 3
-----------------------

(1/1)
/     \
/       \
(1/2)       (2/1)
/  \        /  \
(1/3)  (3/2) (2/3) (3/1)

-----------------------
Calkin Wilf Tree
*/
tree->root = makeTree(level);
// Print tree node value
preorder(tree->root);
return 0;
}``````

#### Output

`` (1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)``
``````// Java program for
// Construct N Level Calkin-Wilf Tree
class TreeNode
{
public int a;
public int b;
public TreeNode left;
public TreeNode right;
public TreeNode(int a, int b)
{
// Set data value
this.a = a;
this.b = b;
// Set node value
this.left = null;
this.right = null;
}
}
public class CalkinWilfTree
{
// Tree Root
public TreeNode root;
public CalkinWilfTree()
{
this.root = null;
}
// This function are constructing a Calkin Wilf Tree
public TreeNode constructTree(int a, int b, int level)
{
if (level == 0)
{
return null;
}
TreeNode node = new TreeNode(a, b);
//  build left and right subtree by using recursively
node.left  = constructTree(a, a + b, level - 1);
node.right = constructTree(a + b, b, level - 1);
return node;
}
public void preorder(TreeNode node)
{
if (node != null)
{
System.out.print(" (" + node.a + "/" + node.b + ")");
preorder(node.left);
preorder(node.right);
}
}
public void makeTree(int level)
{
if (level > 0)
{
this.root = constructTree(1, 1, level);
}
}
public static void main(String[] args)
{
CalkinWilfTree tree = new CalkinWilfTree();
int level = 3;
/*
Level : 3
-----------------------

(1/1)
/     \
/       \
(1/2)       (2/1)
/  \        /  \
(1/3)  (3/2) (2/3) (3/1)

-----------------------
Calkin Wilf Tree
*/
tree.makeTree(level);
// Print tree node value
tree.preorder(tree.root);
}
}``````

#### Output

`` (1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)``
``````// Include header file
#include <iostream>

using namespace std;
// C++ program for
// Construct N Level Calkin-Wilf Tree
class TreeNode
{
public:
int a;
int b;
TreeNode *left;
TreeNode *right;
TreeNode(int a, int b)
{
// Set data value
this->a = a;
this->b = b;
// Set node value
this->left = NULL;
this->right = NULL;
}
};
class CalkinWilfTree
{
public:
// Tree Root
TreeNode *root;
CalkinWilfTree()
{
this->root = NULL;
}
// This function are constructing a Calkin Wilf Tree
TreeNode *constructTree(int a, int b, int level)
{
if (level == 0)
{
return NULL;
}
TreeNode *node = new TreeNode(a, b);
//  build left and right subtree by using recursively
node->left = this->constructTree(a, a + b, level - 1);
node->right = this->constructTree(a + b, b, level - 1);
return node;
}
void preorder(TreeNode *node)
{
if (node != NULL)
{
cout << " (" << node->a << "/" << node->b << ")";
this->preorder(node->left);
this->preorder(node->right);
}
}
void makeTree(int level)
{
if (level > 0)
{
this->root = this->constructTree(1, 1, level);
}
}
};
int main()
{
CalkinWilfTree *tree = new CalkinWilfTree();
int level = 3;
/*
Level : 3
-----------------------
(1/1)
/     \
/       \
(1/2)       (2/1)
/  \        /  \
(1/3)  (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
tree->makeTree(level);
// Print tree node value
tree->preorder(tree->root);
return 0;
}``````

#### Output

`` (1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)``
``````// Include namespace system
using System;
// Csharp program for
// Construct N Level Calkin-Wilf Tree
public class TreeNode
{
public int a;
public int b;
public TreeNode left;
public TreeNode right;
public TreeNode(int a, int b)
{
// Set data value
this.a = a;
this.b = b;
// Set node value
this.left = null;
this.right = null;
}
}
public class CalkinWilfTree
{
// Tree Root
public TreeNode root;
public CalkinWilfTree()
{
this.root = null;
}
// This function are constructing a Calkin Wilf Tree
public TreeNode constructTree(int a, int b, int level)
{
if (level == 0)
{
return null;
}
TreeNode node = new TreeNode(a, b);
//  build left and right subtree by using recursively
node.left = this.constructTree(a, a + b, level - 1);
node.right = this.constructTree(a + b, b, level - 1);
return node;
}
public void preorder(TreeNode node)
{
if (node != null)
{
Console.Write(" (" + node.a + "/" + node.b + ")");
this.preorder(node.left);
this.preorder(node.right);
}
}
public void makeTree(int level)
{
if (level > 0)
{
this.root = this.constructTree(1, 1, level);
}
}
public static void Main(String[] args)
{
CalkinWilfTree tree = new CalkinWilfTree();
int level = 3;
/*
Level : 3
-----------------------
(1/1)
/     \
/       \
(1/2)       (2/1)
/  \        /  \
(1/3)  (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
tree.makeTree(level);
// Print tree node value
tree.preorder(tree.root);
}
}``````

#### Output

`` (1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)``
``````package main
import "fmt"
// Go program for
// Construct N Level Calkin-Wilf Tree
type TreeNode struct {
a int
b int
left * TreeNode
right * TreeNode
}
func getTreeNode(a int, b int) * TreeNode {
var me *TreeNode = &TreeNode {}
// Set data value
me.a = a
me.b = b
// Set node value
me.left = nil
me.right = nil
return me
}
type CalkinWilfTree struct {
// Tree Root
root * TreeNode
}
func getCalkinWilfTree() * CalkinWilfTree {
var me *CalkinWilfTree = &CalkinWilfTree {}
me.root = nil
return me
}
// This function are constructing a Calkin Wilf Tree
func(this *CalkinWilfTree) constructTree(a,
b, level int) * TreeNode {
if level == 0 {
return nil
}
var node * TreeNode = getTreeNode(a, b)
//  build left and right subtree by using recursively
node.left = this.constructTree(a, a + b, level - 1)
node.right = this.constructTree(a + b, b, level - 1)
return node
}
func(this CalkinWilfTree) preorder(node * TreeNode) {
if node != nil {
fmt.Print(" (", node.a, "/", node.b, ")")
this.preorder(node.left)
this.preorder(node.right)
}
}
func(this *CalkinWilfTree) makeTree(level int) {
if level > 0 {
this.root = this.constructTree(1, 1, level)
}
}
func main() {
var tree * CalkinWilfTree = getCalkinWilfTree()
var level int = 3
/*
Level : 3
-----------------------
(1/1)
/     \
/       \
(1/2)       (2/1)
/  \        /  \
(1/3)  (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
tree.makeTree(level)
// Print tree node value
tree.preorder(tree.root)
}``````

#### Output

`` (1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)``
``````<?php
// Php program for
// Construct N Level Calkin-Wilf Tree
class TreeNode
{
public \$a;
public \$b;
public \$left;
public \$right;
public  function __construct(\$a, \$b)
{
// Set data value
\$this->a = \$a;
\$this->b = \$b;
// Set node value
\$this->left = NULL;
\$this->right = NULL;
}
}
class CalkinWilfTree
{
// Tree Root
public \$root;
public  function __construct()
{
\$this->root = NULL;
}
// This function are constructing a Calkin Wilf Tree
public  function constructTree(\$a, \$b, \$level)
{
if (\$level == 0)
{
return NULL;
}
\$node = new TreeNode(\$a, \$b);
//  build left and right subtree by using recursively
\$node->left = \$this->constructTree(\$a, \$a + \$b, \$level - 1);
\$node->right = \$this->constructTree(\$a + \$b, \$b, \$level - 1);
return \$node;
}
public  function preorder(\$node)
{
if (\$node != NULL)
{
echo(" (".\$node->a."/".\$node->b.")");
\$this->preorder(\$node->left);
\$this->preorder(\$node->right);
}
}
public  function makeTree(\$level)
{
if (\$level > 0)
{
\$this->root = \$this->constructTree(1, 1, \$level);
}
}
}

function main()
{
\$tree = new CalkinWilfTree();
\$level = 3;
/*
Level : 3
-----------------------
(1/1)
/     \
/       \
(1/2)       (2/1)
/  \        /  \
(1/3)  (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
\$tree->makeTree(\$level);
// Print tree node value
\$tree->preorder(\$tree->root);
}
main();``````

#### Output

`` (1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)``
``````// Node JS program for
// Construct N Level Calkin-Wilf Tree
class TreeNode
{
constructor(a, b)
{
// Set data value
this.a = a;
this.b = b;
// Set node value
this.left = null;
this.right = null;
}
}
class CalkinWilfTree
{
constructor()
{
this.root = null;
}
// This function are constructing a Calkin Wilf Tree
constructTree(a, b, level)
{
if (level == 0)
{
return null;
}
var node = new TreeNode(a, b);
//  build left and right subtree by using recursively
node.left = this.constructTree(a, a + b, level - 1);
node.right = this.constructTree(a + b, b, level - 1);
return node;
}
preorder(node)
{
if (node != null)
{
process.stdout.write(" (" + node.a + "/" + node.b + ")");
this.preorder(node.left);
this.preorder(node.right);
}
}
makeTree(level)
{
if (level > 0)
{
this.root = this.constructTree(1, 1, level);
}
}
}

function main()
{
var tree = new CalkinWilfTree();
var level = 3;
/*
Level : 3
-----------------------
(1/1)
/     \
/       \
(1/2)       (2/1)
/  \        /  \
(1/3)  (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
tree.makeTree(level);
// Print tree node value
tree.preorder(tree.root);
}
main();``````

#### Output

`` (1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)``
``````#  Python 3 program for
#  Construct N Level Calkin-Wilf Tree
class TreeNode :
def __init__(self, a, b) :
#  Set data value
self.a = a
self.b = b
#  Set node value
self.left = None
self.right = None

class CalkinWilfTree :
#  Tree Root
def __init__(self) :
self.root = None

#  This function are constructing a Calkin Wilf Tree
def constructTree(self, a, b, level) :
if (level == 0) :
return None

node = TreeNode(a, b)
#   build left and right subtree by using recursively
node.left = self.constructTree(a, a + b, level - 1)
node.right = self.constructTree(a + b, b, level - 1)
return node

def preorder(self, node) :
if (node != None) :
print(" (", node.a ,"/", node.b ,")", end = "",sep = "")
self.preorder(node.left)
self.preorder(node.right)

def makeTree(self, level) :
if (level > 0) :
self.root = self.constructTree(1, 1, level)

def main() :
tree = CalkinWilfTree()
level = 3
#    Level : 3
#    -----------------------
#             (1/1)
#            /     \
#           /       \
#       (1/2)       (2/1)
#        /  \        /  \
#    (1/3)  (3/2) (2/3) (3/1)
#    -----------------------
#        Calkin Wilf Tree
tree.makeTree(level)
#  Print tree node value
tree.preorder(tree.root)

if __name__ == "__main__": main()``````

#### Output

`` (1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)``
``````#  Ruby program for
#  Construct N Level Calkin-Wilf Tree
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :a, :b, :left, :right
def initialize(a, b)
#  Set data value
self.a = a
self.b = b
#  Set node value
self.left = nil
self.right = nil
end

end

class CalkinWilfTree
# Define the accessor and reader of class CalkinWilfTree
attr_accessor :root
#  Tree Root
def initialize()
self.root = nil
end

#  This function are constructing a Calkin Wilf Tree
def constructTree(a, b, level)
if (level == 0)
return nil
end

node = TreeNode.new(a, b)
#   build left and right subtree by using recursively
node.left = self.constructTree(a, a + b, level - 1)
node.right = self.constructTree(a + b, b, level - 1)
return node
end

def preorder(node)
if (node != nil)
print(" (", node.a ,"/", node.b ,")")
self.preorder(node.left)
self.preorder(node.right)
end

end

def makeTree(level)
if (level > 0)
self.root = self.constructTree(1, 1, level)
end

end

end

def main()
tree = CalkinWilfTree.new()
level = 3
#    Level : 3
#    -----------------------
#             (1/1)
#            /     \
#           /       \
#       (1/2)       (2/1)
#        /  \        /  \
#    (1/3)  (3/2) (2/3) (3/1)
#    -----------------------
#        Calkin Wilf Tree
tree.makeTree(level)
#  Print tree node value
tree.preorder(tree.root)
end

main()``````

#### Output

`` (1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)``
``````// Scala program for
// Construct N Level Calkin-Wilf Tree
class TreeNode(var a: Int,
var b: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(a: Int, b: Int)
{
// Set data value
// Set node value
this(a, b, null, null)
}
}
class CalkinWilfTree(
// Tree Root
var root: TreeNode)
{
def this()
{
this(null)
}
// This function are constructing a Calkin Wilf Tree
def constructTree(a: Int, b: Int, level: Int): TreeNode = {
if (level == 0)
{
return null;
}
var node: TreeNode = new TreeNode(a, b);
//  build left and right subtree by using recursively
node.left = constructTree(a, a + b, level - 1);
node.right = constructTree(a + b, b, level - 1);
return node;
}
def preorder(node: TreeNode): Unit = {
if (node != null)
{
print(" (" + node.a + "/" + node.b + ")");
preorder(node.left);
preorder(node.right);
}
}
def makeTree(level: Int): Unit = {
if (level > 0)
{
this.root = constructTree(1, 1, level);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: CalkinWilfTree = new CalkinWilfTree();
var level: Int = 3;
/*
Level : 3
-----------------------
(1/1)
/     \
/       \
(1/2)       (2/1)
/  \        /  \
(1/3)  (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
tree.makeTree(level);
// Print tree node value
tree.preorder(tree.root);
}
}``````

#### Output

`` (1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)``
``````// Swift 4 program for
// Construct N Level Calkin-Wilf Tree
class TreeNode
{
var a: Int;
var b: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ a: Int, _ b: Int)
{
// Set data value
self.a = a;
self.b = b;
// Set node value
self.left = nil;
self.right = nil;
}
}
class CalkinWilfTree
{
// Tree Root
var root: TreeNode? ;
init()
{
self.root = nil;
}
// This function are constructing a Calkin Wilf Tree
func constructTree(_ a: Int, _ b: Int, _ level: Int) -> TreeNode?
{
if (level == 0)
{
return nil;
}
let node: TreeNode = TreeNode(a, b);
//  build left and right subtree by using recursively
node.left = self.constructTree(a, a + b, level - 1);
node.right = self.constructTree(a + b, b, level - 1);
return node;
}
func preorder(_ node: TreeNode? )
{
if (node  != nil)
{
print(" (", node!.a ,"/", node!.b ,")", separator:"",
terminator: "");
self.preorder(node!.left);
self.preorder(node!.right);
}
}
func makeTree(_ level: Int)
{
if (level > 0)
{
self.root = self.constructTree(1, 1, level);
}
}
}
func main()
{
let tree: CalkinWilfTree = CalkinWilfTree();
let level: Int = 3;
/*
Level : 3
-----------------------
(1/1)
/     \
/       \
(1/2)       (2/1)
/  \        /  \
(1/3)  (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
tree.makeTree(level);
// Print tree node value
tree.preorder(tree.root);
}
main();``````

#### Output

`` (1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)``
``````// Kotlin program for
// Construct N Level Calkin-Wilf Tree
class TreeNode
{
var a: Int;
var b: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(a: Int, b: Int)
{
// Set data value
this.a = a;
this.b = b;
// Set node value
this.left = null;
this.right = null;
}
}
class CalkinWilfTree
{
// Tree Root
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
// This function are constructing a Calkin Wilf Tree
fun constructTree(a: Int, b: Int, level: Int): TreeNode ?
{
if (level == 0)
{
return null;
}
val node: TreeNode = TreeNode(a, b);
//  build left and right subtree by using recursively
node.left = this.constructTree(a, a + b, level - 1);
node.right = this.constructTree(a + b, b, level - 1);
return node;
}
fun preorder(node: TreeNode ? ): Unit
{
if (node != null)
{
print(" (" + node.a + "/" + node.b + ")");
this.preorder(node.left);
this.preorder(node.right);
}
}
fun makeTree(level: Int): Unit
{
if (level > 0)
{
this.root = this.constructTree(1, 1, level);
}
}
}
fun main(args: Array < String > ): Unit
{
val tree: CalkinWilfTree = CalkinWilfTree();
val level: Int = 3;
/*
Level : 3
-----------------------
(1/1)
/     \
/       \
(1/2)       (2/1)
/  \        /  \
(1/3)  (3/2) (2/3) (3/1)
-----------------------
Calkin Wilf Tree
*/
tree.makeTree(level);
// Print tree node value
tree.preorder(tree.root);
}``````

#### Output

`` (1/1) (1/2) (1/3) (3/2) (2/1) (2/3) (3/1)``

## Time Complexity

The construction of the Calkin-Wilf Tree involves creating each node once, and each node's children are constructed recursively. Therefore, the time complexity of constructing the tree is linear, O(n), where n is the total number of nodes in the tree.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.