Skip to main content

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.

Calkin-Wilf Tree

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_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.

Last updated on by Kalkicode




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.

New Comment