Nidhi's blog

Learning DSA 3

Polkam Srinidhi's photo
Polkam Srinidhi
·

3 min read

Learning DSA 3

Catalan Number: ( standard problem for BST )

Catalan Numbers Series: 1,1,2,5,14,.........

  • nth Catalan Number using Recursion: Catalan numbers satisfy the following recursive formula,

    C0=C1=1 then Cn will be:

    Cn = C(i) + C(n-i-1) for i=0 to n-1 & n>=2

    Time Complexity: O(n2)
    Auxiliary Space: O(n)

  • nth Catalan Number using Binomial Co-efficient: Catalan numbers satisfy the following Binomial formula for nth term Cn,

    Lightbox

    Lightbox

  • Standard problem for BST

    1. To count the number of possible BST's with n Keys

    2. To count the number of FullBT's with n+1 leaves

Fibonacci Number: ( standard problem for Recursion )

Fibonnacci Numbers series: 0,1,2,3,5,7,.............

  • nth Fibonnacci Number using Recursion: Formula,

    f0=0, f1=1 then fn = f(n-1) + f(n-2)

nth Fibonnacci Number using DP: fn[i] = fn[i-1] + fn[i-2];

All possible problems on this: https://leetcode.com/discuss/study-guide/1854405/9-fibonacci-algorithms-the-most-complete-solutions-all-in-one-easy-to-understand

Binomial Co-efficient of n, k (nCk = C(n, k):

initial conditions, C(0, 0)=C(n, 0)=C(n,n)=1

  • FOR k>n, C(n, k)=C(n, n-k)

  • using RECURSION: C(n, k) = C(n-1, k-1) + C(n-1, k)

    Time Complexity: O(n*max(k,n-k))

    Auxiliary Space: O(n*max(k,n-k))

  • using DP: C[i][j] = C[i-1][j-1] + C[i-1][j] (2D array)

Trees Introduction:

Binary Tree vs Binary Search Tree:

S. No.Basis of ComparisonBINARY TREEBINARY SEARCH TREE
1.DefinitionBINARY TREE is a nonlinear data structure where each node can have at most two child nodes.BINARY SEARCH TREE is a node based binary tree that further has right and left subtree that too are binary search tree.
2.TypesFull binary tree, Complete binary tree, Extended Binary tree and moreAVL tree, Splay Tree, T-trees and more
3.StructureIn BINARY TREE there is no ordering in terms of how the nodes are arrangedIn BINARY SEARCH TREE the left subtree has elements less than the nodes element and the right subtree has elements greater than the nodes element.
4.Data RepresentationData Representation is carried out in a hierarchical format.Data Representation is carried out in the ordered format.
5.Duplicate ValuesBinary trees allow duplicate values.Binary Search Tree does not allow duplicate values.
6.SpeedThe speed of deletion, insertion, and searching operations in Binary Tree is slower as compared to Binary Search Tree because it is unordered.Because the Binary Search Tree has ordered properties, it conducts element deletion, insertion, and searching faster.
7.ComplexityTime complexity is usually O(n).Time complexity is usually O(logn).
8.ApplicationIt is used for retrieval of fast and quick information and data lookup.It works well at element deletion, insertion, and searching.
9.UsageIt serves as the foundation for implementing Full Binary Tree, BSTs, Perfect Binary Tree, and others.It is utilized in the implementation of Balanced Binary Search Trees such as AVL Trees, Red Black Trees, and so on.

Traversals in Binary tree:

A Tree Data Structure can be traversed in following ways:

  1. Depth First Search or DFS

    1. Inorder Traversal (L, R, Ri)

    2. Preorder Traversal (R, L, Ri)

    3. Postorder Traversal (L, Ri, R)

  1. Level Order Traversal or Breadth First Search or BFS

    1. Boundary Traversal : “20 8 4 10 14 25 22”

    2. Diagonal Traversal :

Diagonal Traversal of binary tree : 8 10 14 3 6 7 13 1 4

Problems tried:

  1. https://leetcode.com/problems/unique-binary-search-trees/description/

Too less, but worked

Sources: https://www.youtube.com/watch?v=CMaZ69P1bAc
https://www.geeksforgeeks.org/

Beginner Developers#DSAinjavaProgramming BlogsProductivity#growthtips