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
- Define a
TreeNode
structure witha
,b
,left
, andright
pointers. - Define a
CalkinWilfTree
structure with aroot
pointer. - Implement a
newTree
function that creates a new instance ofCalkinWilfTree
. - Implement a
newNode
function that creates a new instance ofTreeNode
with givena
andb
values. - 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.
- If the level is 0, return
- Implement a
makeTree
function that initializes the tree construction with the root fraction1/1
. - Implement a
preorder
function that traverses the tree in preorder and prints the fractions. - 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_reader :a, :b, :left, :right
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_reader :root
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.
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.
New Comment