Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Data Structure

Trees

PreviousHash TablesNextGraphs

Last updated 1 year ago

A Tree data structure is a hierarchical way to organize data, with a topmost node called the root and connected nodes called children. Each node can have multiple children, forming a recursive structure.

There are several types of tree data structures, each with its own unique properties and use cases:

  1. Binary Tree: A tree data structure in which each node has at most two children, typically referred to as the left child and the right child.

  2. Ternary Tree: A tree data structure where each node has at most three children, usually distinguished as left, mid, and right.

  3. N-ary Tree (Generic Tree): A tree data structure where each node can have n number of children.

  4. Binary Search Tree: A binary tree in which for each node, the values of all the nodes in its left subtree are lesser or equal and the values of all nodes in right subtree are greater.

  5. AVL Tree: A self-balancing binary search tree where the difference between heights of left and right subtrees cannot be more than one for all nodes.

  6. Red-Black Tree: A kind of self-balancing binary search tree where each node contains an extra bit for denoting the color of the node, either red or black.

  7. B-Tree: A self-balancing search tree, mainly used in databases and file systems, where a node can have more than two children.

  8. Heap: It is a special tree-based data structure where the tree is a complete binary tree. It satisfies the heap property, which states that the key of each node is always greater than or equal to (in a Max Heap) or less than or equal to (in a Min Heap) the keys of its children.

  9. Binary Heap: It is a complete binary tree used to efficiently store data and retrieve the max or min element. It obeys the property that the root of any subtree has a higher (or lower, based on the type of heap) value than all the nodes in its subtree. It comes in two forms: Min Heap and Max Heap. In a Min Heap, the key at the root must be minimum among all keys present in the Binary Heap, and in a Max Heap, the key at the root must be maximum. A binary heap is a complete binary tree. All levels of the tree, except possibly the last one (deepest) are fully filled. Binary Heaps are used in various applications like implementing priority queues, in operating systems for prioritizing processes, in networking for prioritizing packets for timely delivery, in databases for indexing data, and in pathfinding algorithms.

  10. Trie: A Trie, also known as a prefix tree, is a tree-based data structure used for efficiently storing and retrieving strings. It is particularly useful for tasks like autocomplete or searching for words with a given prefix.

Operations of the Trees in data structure

There are some operations of the Trees in the data structure:

  • Traversal: Visit each node in the tree in a specific order. Common traversal methods include Preorder, Inorder, and Postorder.

  • Insertion: Insert a new node into the tree.

  • Deletion: Delete a node into the tree.

  • Search: Search for a specific node in the tree.

  • Update: Update a node into the tree.

  • Sort: This operation arranges elements in a specific order.

  • Height of Tree: Calculate the height or depth of the tree.

  • Level of a Node: Determine the level of a given node.

  • Find Parent: Find the parent of a given node.

  • Find Children: Find the children of a given node.

  • Find Siblings: Find the siblings of a given node.

  • Find all Leaf Nodes: Find all nodes in the tree that have no children.

Complexity Table

Tree
Access
Search
Insertion
Deletion

Simple Tree

O(N)

O(N)

O(N)

O(N)

Ternary Search Tree

N/A

O(H)

O(H)

O(H)

Binary Tree

O(N)

O(N)

O(N)

O(N)

Binary Search Tree

O(N)

O(N)

O(N)

O(N)

AVL Tree

O(log N)

O(log N)

O(log N)

O(log N)

Red-Black Tree

O(log N)

O(log N)

O(log N)

O(log N)

B-Tree

O(log N)

O(log N)

O(log N)

O(log N)

Heap

O(1)

O(N)

O(log N)

O(log N)

Trie

N/A

O(L)

O(L)

O(L)