Non-Recursive Inverting of Binary Tree in Rust

Overview

Non-Recursive Inverting of Binary Tree in Rust

The idea is to implement the classical Inverting of Binary Tree but without using recursion.

Quick Start

$ rustc main.rs
$ ./main

Main Idea

The Main Idea is to basically simulate the recursion by managing two stacks: one for the arguments (arg_stack) and one for the return values (ret_stack). The arg_stack contains a sequence of two kinds of actions:

#[derive(Debug)]
enum Action<T, U> {
    Call(T),
    Handle(U),
}

Call simulates the recursive function call with the given arguments T, Handle allows to postpone the handling of the return values on ret_stack to achieve a specific order of execution that is usually achieved by using recursive functions.

This forms a general purpose framework that enables us to convert any (I believe so, can't formally prove it) recursive function into a non-recursive one.

Let's take a look at a simple recursive function that calculates n-th Fibonacci number:

fn fib(n: usize) -> usize {
    if n < 2 {
        n
    } else {
        fib(n - 1) + fib(n - 2)
    }
}

This is how you would implement such function in a non-recursive fashion using the aforementioned framework:

fn fib_nonrec(n: usize) -> usize {
    let mut arg_stack = Vec::<Action<usize, ()>>::new();
    let mut ret_stack = Vec::<usize>::new();

    use Action::*;
    arg_stack.push(Call(n));
    while let Some(action) = arg_stack.pop() {
        println!("action = {:?}", &action);
        match action {
            Call(n) => if n < 2 {
                ret_stack.push(n)
            } else {
                arg_stack.push(Handle(()));
                arg_stack.push(Call(n - 2));
                arg_stack.push(Call(n - 1));
            },

            Handle(()) => {
                let a = ret_stack.pop().unwrap();
                let b = ret_stack.pop().unwrap();
                ret_stack.push(a + b);
            },
        }
        println!("arg_stack = {:?}", &arg_stack);
        println!("ret_stack = {:?}", &ret_stack);
        println!("------------------------------")
    }

    ret_stack.pop().unwrap()
}

Calling fib_nonrec(3) generates the following log:

action = Call(3)
arg_stack = [Handle(()), Call(1), Call(2)]
ret_stack = []
------------------------------
action = Call(2)
arg_stack = [Handle(()), Call(1), Handle(()), Call(0), Call(1)]
ret_stack = []
------------------------------
action = Call(1)
arg_stack = [Handle(()), Call(1), Handle(()), Call(0)]
ret_stack = [1]
------------------------------
action = Call(0)
arg_stack = [Handle(()), Call(1), Handle(())]
ret_stack = [1, 0]
------------------------------
action = Handle(())
arg_stack = [Handle(()), Call(1)]
ret_stack = [1]
------------------------------
action = Call(1)
arg_stack = [Handle(())]
ret_stack = [1, 1]
------------------------------
action = Handle(())
arg_stack = []
ret_stack = [2]
------------------------------

The top of the stacks is on the right.

Notice how the arg_stack grows until it exhausts n and shrinks back computing the final result into the ret_stack. This is basically the simulation of the recursive process.

The resulting code is admittedly bigger, less readable and more difficult to extend, so I do not generally recommend to develop in this style. This entire example was created as a coding exercise. Although this approach might be useful for doing very deep recursion to prevent stack overflows, since Vec<T> can extend for as long as there is available memory and the call stack is usually limited.

You might also like...
A syntax highlighter for Node powered by Tree Sitter. Written in Rust.

tree-sitter-highlight A syntax highlighter for Node.js powered by Tree Sitter. Written in Rust. Usage The following will output HTML: const treeSitter

Basic template for an out-of-tree Linux kernel module written in Rust.

Rust out-of-tree module This is a basic template for an out-of-tree Linux kernel module written in Rust. Please note that: The Rust support is experim

An Rust implementation of the Modified Merkle Patricia Tree described by ETH Yellow Paper

Merkle Patricia Tree的Rust实现 博客文章:https://dere.press/2022/01/24/eth-trie/ 本实现参考下列项目: https://ethereum.github.io/yellowpaper/paper.pdf https://github.co

Build Abstract Syntax Trees and tree-walking models quickly in Rust.

astmaker Build Abstract Syntax Trees and tree-walking models quickly in Rust. Example This example creates an AST for simple math expressions, and an

Like grep, but uses tree-sitter grammars to search

tree-grepper Works like grep, but uses tree-sitter to search for structure instead of strings. Installing This isn't available packaged anywhere. That

Tree-sitter - An incremental parsing system for programming tools

tree-sitter Tree-sitter is a parser generator tool and an incremental parsing library. It can build a concrete syntax tree for a source file and effic

A tree-sitter based AST difftool to get meaningful semantic diffs
A tree-sitter based AST difftool to get meaningful semantic diffs

diffsitter Disclaimer diffsitter is very much a work in progress and nowhere close to production ready (yet). Contributions are always welcome! Summar

k-dimensional tree

kd-tree k-dimensional tree in Rust. Fast, simple, and easy to use. Usage // construct kd-tree let kdtree = kd_tree::KdTree::build_by_ordered_float(vec

Semantic find-and-replace using tree-sitter-based macro expansion

Semantic find-and-replace using tree-sitter-based macro expansion

Owner
Tsoding
Recreational Programming
Tsoding
Traversal of tree-sitter Trees and any arbitrary tree with a TreeCursor-like interface

tree-sitter-traversal Traversal of tree-sitter Trees and any arbitrary tree with a TreeCursor-like interface. Using cursors, iteration over the tree c

Sebastian Mendez 12 Jan 8, 2023
As-tree - Print a list of paths as a tree of paths 🌳

as-tree Print a list of paths as a tree of paths. For example, given: dir1/foo.txt dir1/bar.txt dir2/qux.txt it will print: . ├── dir1 │ ├── foo.tx

Jake Zimmerman 396 Dec 10, 2022
Minimal recursive "truncate file/directory names to meet requirements" tool

trunc_filenames ssokolow@monolith ~ % trunc_filenames --help trunc_filenames 0.1.0 Rename files and directories to fit length limits. WARNING: Will n

Stephan Sokolow 2 Nov 20, 2022
A language parser tool to build recursive descent top down parser.

lang-pt A language parser tool to generate recursive descent top down parser. Overview Parsers written for the languages like Javascript are often cus

Creative Forest 7 Jan 4, 2023
Recursive-OVOTE: OVOTE enjoying Plonky2 recursion

rovote: recursive ovote Recursive-OVOTE: OVOTE enjoying Plonky2 recursion. Note: this repo is an experiment, do not use in production. The inner & out

Aragon ZK Research 6 Apr 2, 2023
Non-interactive nREPL client for shell scripts and command-line

nreplops-tool (nr) nreplops-tool (nr) is a non-interactive nREPL client designed to be used in shell scripts and on the command-line. Early α warning:

Matti Hänninen 3 Jul 1, 2022
Cost saving K8s controller to scale down and up of resources during non-business hours

Kube-Saver Motivation Scale down cluster nodes by scaling down Deployments, StatefulSet, CronJob, Hpa during non-business hours and save $$, but if yo

Mahesh Rayas 5 Aug 15, 2022
No non-sense dotfiles linker

dotlink A simple program that can help you link all your dotfiles in place. Supports multiple presets, in order to avoid linking every file in every m

null 26 Apr 19, 2023
a simple, non-self-describing data-interchange format.

rust-fr 'rust-fr' (aka rust for real) is a simple, non-self-describing data-interchange format. installation You can use either of these methods. Add

Ayush 4 Feb 28, 2024
Prefix tree implemented in Rust.

Prefix tree implemented in rust. A simple library that provides a prefix tree (trie) implementation. It uses generic types for both keys and values. p

Bailey 0 Dec 8, 2021