Amazing fractal tree on bash

getftree.sh

# @see https://www.hackerrank.com/challenges/fractal-trees-all
# Creating a Fractal Tree from Y-shaped branches
#
# This challenge involves the construction of trees, in the form of ASCII Art.
#
# We have to deal with real world constraints, so we cannot keep repeating the pattern infinitely.
# So, we will provide you a number of iterations, and you need to generate the ASCII version
# of the Fractal Tree for only those many iterations (or, levels of recursion). A few samples are provided below.
#
# Input Format
# A single integer, N.
#
# Constraints
# N <= 5
#
# Output Format
# The Nth iteration of the Fractal Tree, as shown above.
# It should be a matrix of 63 rows and 100 columns. (i.e. 6300 printable characters)
# It should be composed entirely of underscores and ones, in a manner similar to the examples provided.
# Do not include any extra leading or trailing spaces.
#____________________________________________________________________________________________________
#__________________1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1___________________
#___________________1___1___1___1___1___1___1___1___1___1___1___1___1___1___1___1____________________
#___________________1___1___1___1___1___1___1___1___1___1___1___1___1___1___1___1____________________
#____________________1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____________________
#_____________________1_______1_______1_______1_______1_______1_______1_______1______________________
#_____________________1_______1_______1_______1_______1_______1_______1_______1______________________
#_____________________1_______1_______1_______1_______1_______1_______1_______1______________________
#______________________1_____1_________1_____1_________1_____1_________1_____1_______________________
#_______________________1___1___________1___1___________1___1___________1___1________________________
#________________________1_1_____________1_1_____________1_1_____________1_1_________________________
#_________________________1_______________1_______________1_______________1__________________________
#_________________________1_______________1_______________1_______________1__________________________
#_________________________1_______________1_______________1_______________1__________________________
#_________________________1_______________1_______________1_______________1__________________________
#_________________________1_______________1_______________1_______________1__________________________
#__________________________1_____________1_________________1_____________1___________________________
#___________________________1___________1___________________1___________1____________________________
#____________________________1_________1_____________________1_________1_____________________________
#_____________________________1_______1_______________________1_______1______________________________
#______________________________1_____1_________________________1_____1_______________________________
#_______________________________1___1___________________________1___1________________________________
#________________________________1_1_____________________________1_1_________________________________
#_________________________________1_______________________________1__________________________________
#_________________________________1_______________________________1__________________________________
#_________________________________1_______________________________1__________________________________
#_________________________________1_______________________________1__________________________________
#_________________________________1_______________________________1__________________________________
#_________________________________1_______________________________1__________________________________
#_________________________________1_______________________________1__________________________________
#_________________________________1_______________________________1__________________________________
#_________________________________1_______________________________1__________________________________
#__________________________________1_____________________________1___________________________________
#___________________________________1___________________________1____________________________________
#____________________________________1_________________________1_____________________________________
#_____________________________________1_______________________1______________________________________
#______________________________________1_____________________1_______________________________________
#_______________________________________1___________________1________________________________________
#________________________________________1_________________1_________________________________________
#_________________________________________1_______________1__________________________________________
#__________________________________________1_____________1___________________________________________
#___________________________________________1___________1____________________________________________
#____________________________________________1_________1_____________________________________________
#_____________________________________________1_______1______________________________________________
#______________________________________________1_____1_______________________________________________
#_______________________________________________1___1________________________________________________
#________________________________________________1_1_________________________________________________
#_________________________________________________1__________________________________________________
#_________________________________________________1__________________________________________________
#_________________________________________________1__________________________________________________
#_________________________________________________1__________________________________________________
#_________________________________________________1__________________________________________________
#_________________________________________________1__________________________________________________
#_________________________________________________1__________________________________________________
#_________________________________________________1__________________________________________________
#_________________________________________________1__________________________________________________
#_________________________________________________1__________________________________________________
#_________________________________________________1__________________________________________________
#_________________________________________________1__________________________________________________
#_________________________________________________1__________________________________________________
#_________________________________________________1__________________________________________________
#_________________________________________________1__________________________________________________
#_________________________________________________1__________________________________________________

#!/usr/bin/env bash
read N

MAX_N=5
BLANK_N=$((MAX_N - N))

COLS=100
ROWS=64
LEAFS_NUMBER=1

LINE_BREAK=$'\\n'
BRANCH="1"
BLANK="_"

draw_sub_tree ()
{
	local SUB_TREE_HEIGHT=$1
	local ROOTS_NUMBER=$2

    local ROW_INDEX=${SUB_TREE_HEIGHT}
    local SUB_TREE=""

	while [ ${ROW_INDEX} -gt 0 ]
    do
        SUB_TREE="${SUB_TREE}$(draw_line ${SUB_TREE_HEIGHT} ${ROW_INDEX} ${ROOTS_NUMBER})"
        ROW_INDEX=$((ROW_INDEX - 1))
    done

	echo "$SUB_TREE"
}

draw_line ()
{
    #1. Evaluate all parameters

    local SUB_TREE_HEIGHT=$1
    local ROW_INDEX=$2
	local ROOTS_NUMBER=$3
	local LEAFS_NUMBER=${ROOTS_NUMBER}
	local LINE=""

    [ ${ROW_INDEX} -gt $((SUB_TREE_HEIGHT / 2)) ]
	local IS_LEAF_PART=$?

    local LEFT_SIDE_LENGTH=0
    local RIGHT_SIDE_LENGTH=0
    local BETWEEN_LEAFS_LENGTH=0
    local BETWEEN_ROOTS_LENGTH=0

    # Leafs part of tree
	if [ ${IS_LEAF_PART} -eq 0 ]; then
		LEAFS_NUMBER=$((ROOTS_NUMBER * 2))

        BETWEEN_LEAFS_LENGTH=$(( (ROW_INDEX - SUB_TREE_HEIGHT / 2) * 2 - 1 ))

        if [ ${ROOTS_NUMBER} -eq 1 ]; then
            BETWEEN_ROOTS_LENGTH=0
        else
            BETWEEN_ROOTS_LENGTH=$(( (SUB_TREE_HEIGHT * 2) - 1 - (BETWEEN_LEAFS_LENGTH + 1) ))
        fi

        LEFT_SIDE_LENGTH=$(( (COLS - LEAFS_NUMBER - (BETWEEN_LEAFS_LENGTH * (LEAFS_NUMBER / 2)) - (BETWEEN_ROOTS_LENGTH * (ROOTS_NUMBER - 1)) ) / 2 ))
	# Root part of tree
	else
        if [ ${ROOTS_NUMBER} -eq 1 ]; then
            BETWEEN_ROOTS_LENGTH=0
        else
            BETWEEN_ROOTS_LENGTH=$(( (SUB_TREE_HEIGHT * 2) - 1 ))
        fi

	    BETWEEN_LEAFS_LENGTH=0

        LEFT_SIDE_LENGTH=$(( (COLS - ROOTS_NUMBER - (BETWEEN_ROOTS_LENGTH * (ROOTS_NUMBER - 1)) ) / 2 ))
	fi

    RIGHT_SIDE_LENGTH=$((LEFT_SIDE_LENGTH + 1))

    #2. Build sub tree

    LINE="${LINE}$(for ((i=0; i<$LEFT_SIDE_LENGTH; i++)); do echo -n ${BLANK}; done)"

    for ((i=0; i<${LEAFS_NUMBER}; i++))
	do
        LINE="${LINE}${BRANCH}"

	    if [ ${i} -eq $((LEAFS_NUMBER - 1)) ]; then
	        break
		elif [ $(($i % 2)) -eq 0 ] && [ ${IS_LEAF_PART} -eq 0 ]; then
            LINE="${LINE}$(for ((i=0; i<$BETWEEN_LEAFS_LENGTH; i++)); do echo -n ${BLANK}; done)"
		else
            LINE="${LINE}$(for ((i=0; i<$BETWEEN_ROOTS_LENGTH; i++)); do echo -n ${BLANK}; done)"
		fi
	done

    LINE="${LINE}$(for ((i=0; i<$RIGHT_SIDE_LENGTH; i++)); do echo -n ${BLANK}; done)"

	echo "${LINE}${LINE_BREAK}"
}

while [ ${N} -gt 0  ]
do
	ROWS=$((ROWS / 2))

	TREE="$(draw_sub_tree ${ROWS} ${LEAFS_NUMBER})${TREE}"

	LEAFS_NUMBER=$((LEAFS_NUMBER * 2))

	N=$((N - 1))
done

while [ ${BLANK_N} -ge 0  ]
do
	ROWS=$((ROWS / 2))

    for ((i=0; i<${ROWS}; i++))
	do
        TREE="$(for ((i=0; i<${COLS}; i++)); do echo -n ${BLANK}; done)${LINE_BREAK}${TREE}"
	done

	BLANK_N=$((BLANK_N - 1))
done

echo -e "$TREE"

Masterpiece!
💃 🌟 👑

Hey @nkapliev was going through your code. I ran it successfully and was trying to understand it.
I have few questions regarding the code one of which is why You have initialised ROWS=64 ?
Line92

Hey @NupurThakur27,

I ran it successfully and was trying to understand it.

Me too :)
Based on my own comment Masterpiece! it seems that I did understand it back then. But you know, it was a while ago, sorry.

why You have initialised ROWS=64

This is kind of a starting point. You need to specify size of the tree.
I guess you could set

ROWS=2^(N+1)-1

But do not take my word on that 😅

Nice code, please also check my code: https://raw.githubusercontent.com/pancudaniel7/alg/master/shell/input_render_tree.sh