Join Raghavendra Dixit for an in-depth discussion in this video Height of a binary tree, part of Introduction to Data Structures & Algorithms in Java.
- [Instructor] Now, let's find the height of a binary tree,…assuming that it is balanced.…And by height of the tree we basically mean,…how many layers does it have?…So, for example, this is layer one,…which just has one node.…Then this is layer two, which has two nodes.…Then layer three has four nodes, and so on.…So if we have H layers in a binary tree,…we say that H is the height of that tree.…And in that H layer, we have two base…to the bottom, H minus one nodes, right?…So in all, how many nodes do we have?…Well we have one plus two…plus four plus one, all the way…up to two base to the bottom, H minus one.…
But now we need to find this height…in terms of the total number of nodes,…which is N.…So we can right this expression,…and the left hand side…is just a geometry convention, right?…And what is its sum?…With this, two base to the bottom, H minus one,…divided by two minus one.…And this is equal to N.…
And from here we get H two B…of the order of log base two of N, alright?…
Note: This course was created by Packt Publishing. We are pleased to host this training in our library.
- Why study data structures and algorithms?
- How to calculate the time complexity
- Using Big O notation
- Using basic sorting and search algorithms
- Searching elements in unordered arrays and ordered arrays
- Implementing a linked list in Java
- Implementing stacks using arrays
- Queues using arrays
- Binary search trees
- Representing heaps using arrays
Skill Level Intermediate
1. Introduction to Algorithms
2. Analysis of Algorithms
3. Basic Sorting and Search Algorithms
4. Linked Lists
5. Stacks and Queues
7. Binary Search Trees
8. More Sorting Algorithms
- Mark as unwatched
- Mark all as unwatched
Are you sure you want to mark all the videos in this course as unwatched?
This will not affect your course history, your reports, or your certificates of completion for this course.Cancel
Take notes with your new membership!
Type in the entry box, then click Enter to save your note.
1:30Press on any video thumbnail to jump immediately to the timecode shown.
Notes are saved with you account but can also be exported as plain text, MS Word, PDF, Google Doc, or Evernote.