Binary Tree Algorithm

The Binary Tree Inorder Traversal Algorithm is a depth-first traversal technique used to visit all the nodes in a binary tree in a specific order. In this algorithm, the nodes of the binary tree are visited in the following sequence: first, the left subtree is traversed, then the root node is visited, and finally, the right subtree is traversed. This sequence is applied recursively for each subtree in the binary tree. The result of the inorder traversal is a list of the tree's nodes sorted in ascending order, which makes this algorithm particularly useful when working with binary search trees. To implement the inorder traversal algorithm, one can use either a recursive or an iterative approach. In the recursive approach, the algorithm first calls itself for the left subtree of the root node, then it processes the root node by adding its value to the resulting list, and finally, it calls itself for the right subtree of the root node. The iterative approach, on the other hand, uses a stack data structure to keep track of the nodes yet to be visited. Starting with the root node, it pushes all the nodes in the left subtree onto the stack, then pops and processes the top node, and repeats the process for the right subtree. This iterative approach can be more efficient in terms of memory usage, as it eliminates the overhead of recursive function calls.
/*
 * Copyright (c) 2017 Kotlin Algorithm Club
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

package com.algorithmexamples.datastructures.tree

import com.algorithmexamples.datastructures.Queue

class BinaryTree(var value: Int, var left: BinaryTree?, var right: BinaryTree?) {
    constructor(value: Int): this(value, null, null)

    fun size(): Int {
        var size = 1
        if (left != null) {
            size += left!!.size()
        }
        if (right != null) {
            size += right!!.size()
        }
        return size
    }

    fun height(): Int {
        val left = if (left == null) 0 else left!!.height()
        val right = if (right == null) 0 else right!!.height()
        return maxOf(left, right) + 1
    }

    fun add(value: Int) {
        // adds the on the first empty level
        val queue = Queue<BinaryTree>()
        queue.add(this)
        while (!queue.isEmpty()) {
            val x = queue.poll()
            if (x.left == null) {
                x.left = BinaryTree(value)
                return
            } else if (x.right == null) {
                x.right = BinaryTree(value)
                return
            } else {
                queue.add(x.left!!)
                queue.add(x.right!!)
            }
        }
    }
}

LANGUAGE:

DARK MODE: