How to Find the Branching Factor of a Tree

algorithm binary-search-tree search-tree
blazing picture blazing · Dec 13, 2017 · Viewed 21.8k times · Source

A particular search tree has 6 nodes at level 3. At the next level, there are 24 nodes. What is the branching factor at level 3?

The answer is 4, but can someone tell me why, I thought that it was 2.

Answer

Anis picture Anis · Dec 13, 2017

From Wikipedia:

In computing, tree data structures, and game theory, the branching factor is the number of children at each node, the outdegree. If this value is not uniform, an average branching factor can be calculated.

You have 6 nodes at level 3, 24 nodes at level 4, so the average number of children per node at level 3 is 24/6=4.

Related questions

Finding height in Binary Search Tree

I was wondering if anybody could help me rework this method to find the height of a binary search tree. So far, my code looks like this. However, the answer I'm getting is larger than the actual height by 1. But …

Read More
Heap vs Binary Search Tree (BST)

What is the difference between a heap and BST? When to use a heap and when to use a BST? If you want to get the elements in a sorted fashion, is BST better over heap?

Read More
How do you validate a binary search tree?

I read on here of an exercise in interviews known as validating a binary search tree. How exactly does this work? What would one be looking for in validating a binary search tree? I have written a basic search tree, …

Read More