CODEWITHSUNDEEP
c++treebinary-treebinary-search-tree
MipsMoreLikeWhips
MipsMoreLikeWhips

Reputation: 147

Node formula of a different kind of binary search tree

I'm trying to find the max number of nodes in a tree that is defined as follows:

The root can have at most 2 children. Each subtree on the left can have at most L children. Each subtree on the right can have at most R children.

I know the formula for finding the number nodes in a binary tree is 2^h-1, where h is the amount of levels in the tree.

How would this be approached in layman's terms? (I am not extremely mathy.)

Upvotes: 1

Views: 426

Answers (1)

Rahul Manne
Rahul Manne

Reputation: 1249

So more formally, you are trying to find the number of nodes in a binary search tree such that the root of the tree has two children, and each subtree on the left has at most l children and each subtree on the right has r children.

We can consider the left and right trees separately, since they don't affect each other's height. Disregarding the root, let's call the left subtree of the root L and let's call the right subtree of the root R. L holds the invariant that each node in L cannot have more than l children. Similarly, each node in R cannot have more than r children.

Let's construct two function, b and c, that take height h and output the maximum number of nodes in L or R respectively. 

b(h) = if h = 1 then 1 else l * b(h - 1)
c(h) = if h = 1 then 1 else r * b(h - 1)

Now, we can construct function a that takes height h and outputs the maximum nodes of the tree you defined. 

a(h) = if h = 1 then 1 else (b(h - 1) + c(h - 1))

Now, we want to find a closed form for a. Let's start by finding the closed forms for b and c.

Given positive height h, since l is being repeatedly multiplied except for the first case,

b(h) = l^(h - 1)
c(h) = r^(h - 1)
a(h) = if h = 1 then 1 else (l^(h - 1) + r^(h - 1))

I'm not sure if you wanted to also consider h = 1 within the closed form for a, but given h > 1, the formula for finding the maximum number of nodes of the binary search tree you defined, is

l^(h - 1) + r^(h - 1)

Upvotes: 2

Related Questions